内容发布更新时间 : 2024/6/16 20:23:04星期一 下面是文章的全部内容请认真阅读。

第六章 图的基本概念

P206习题

1．画出具有4个顶点的所有无向图(同构的只算一个)。

11个

2．画出具有3个顶点的所有有向图(同构的只算一个)。

16个

3．画出具有4个、6个、8个顶点的三次图。 略

4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。

把实际问题转化为图论问题，然后用握手定理的推论。

P209习题

1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有圈？

若u与v间有两条不同的通道，G中无圈 若u与v间有两条不同的迹，G中有圈

2．证明：一个连通的(p，q)图中q≥p-1。 数学归纳法

3．设G是一个（p，q）图，且q?(p?1)(p?2)/2，则G是连通的。

6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。 证明：把实际问题转化为图论问题，就和下面的题一样了。

8．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。 这两个题和这个题一样的证明方法。

P216习题

1．证明：若图G不是连通图，则Gc 是连通图。

2．证明：每一个自补图有4n或4n+1个顶点。

P228习题

1.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。

下图中任意一对不邻接的顶点u和v，均有：degu+degv≥9。

2．试求Kp中不同的哈密顿圈的个数。

(p-1)!/2

4．完全偶图Km，n为哈密顿图的充分必要条件是什么？

10．证明具有奇数顶点的偶图不是哈密顿图。