离散数学复习提纲（图论）
1. 判别图6－1的两幅图是否可以一笔画出？
解 在图6－1(a ) 中，
deg(v 1)=deg(v 2)=deg(v 3)＝3
有两个以上的结点的度为3. 故在(a )中不存在欧拉通路，不能一笔画出.
在图6－1(b ) 中，deg(A )=2, deg(B ) =deg(C )= deg(D )=4，deg(E ) =deg(F )=3
只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出. 一条欧拉通路，如EDBEFCABCDF .
2． 画出具有下列条件的有5个结点的无向图.
(1) 不是哈密顿图，也不是欧拉图； (2) 有哈密顿回路，没有欧拉回路； (3) 没有哈密顿回路，有欧拉回路； (4) 是哈密顿图，也是欧拉图. 解 作图如图6－3(不唯一).
(1) (2) (3) (4) 在图(1)中，可以走遍5个点，但不是回路，无哈密顿回路，故不是哈密顿图。
无论指定怎样的方向，可以走遍所有边，但不是回路，不能构成欧拉路。
在图(2)中，容易找出走遍5个点的回路，即有哈密顿回路，故是哈密顿图。
但是构成
回路，要么出现重复边，要么漏掉边，即不存在欧拉回路，因此不是欧拉图。
在图(3)中，不重复地走遍5个点是不可能的，故不是哈密顿图。
如指定右边垂直边方
向向上，就可以画出一个走遍所有的边，又不重复的回路，所以有欧拉回路，故是哈欧拉图。
v 4 v 5 E F
A
v 2 v 3 B C v 1 D （a ） (b ) 图6－1
第1个面，边界为a b e a ，次数为3；第2个面，边界为b d e b ，次数为3； 第3个面，边界为a b c a ，次数为3；第4个面，边界为a d e a ，次数为3； 第5个面，边界为a c b d a ，次数为4。
（b ）图中共有两个面，第1个面，边界为 g f c d e f g ，次数为6； 第2个面，边界为 a b c d e f c b a ，次数为8。
4．在具有n 个结点的完全图K n 中，需要删去多少条边才能得到树？
解 n 个结点的完全图共有2
)
1(2
-=
n n C n 条边，而n 个结点的树共有n －1条边. 因此需要删去2
)2)(1()1(2
--=--n n n C n 条边后方可得到树.
5．设G 是图，无回路，但若外加任意一条边于G 后，就形成一回路. 试证明G 必为树.
证明 由树的定义可知，只需证G 连通即可. 任取不相邻两点u ,v , 由题设，加上边<u ,v >就形成一回路，于是去掉边<u ,v >,从u 到v 仍有路u ,…,v ，即u ,v 连通，由u ,v 的任意性可知，G 是连通的，故G 必是树.
6．如图6－5是有6个结点a ,b ,c ,d ,e ,f
的带权无向图，各边的权如图所示. 试求 其最小生成树.
解 构造连通无圈的图，即最小生成树，
b ∙ 23 1 15
c ∙ 25 ∙ a 4 ∙ f 28 9 16 3
d ∙ 15 ∙
e 图6－5
用克鲁斯克尔算法：
第一步： 取ab ＝1；第二步： 取af =4；第三步： 取fe =3；第四步： 取ad =9； 第五步： 取bc =23.
如图6－6。
权为1+4+3+9+23=30
7．试画出一棵带权1，2，2，3，4，5，5，6，7，8，10的最优二叉树。
解：最优二叉树如下：
9．试证明下图中两个无向图是不同构的。
10．一个简单无向图同构于它的补图，称为自补图，证明其结点必是4k 或者4k+1.
11．非平凡的树至少有两个叶子。
12．证明: 在任何n (n ≥2)个顶点的简单图G 中，至少有两个顶点具有相同的度。
证 如果G 有两个孤立顶点，那么它们便是具有相同的度的两个顶点。
如果G 恰有一个孤立顶点，那么我们可对有n – 1 个顶点但没有孤立顶点的G’（它由G 删除孤立顶点后得到）作下列讨论。
不妨设G 没有孤立顶点，那么G 的n 个顶点的度数应是：1，2，3，…，n –1 这n –1种
b ∙ 23 1
c ∙ ∙ a 4 ∙ f 9 3
d ∙ ∙
e 图6－6
可能之一，因此必定有两个顶点具有相同的度。
13．n 个城市间有m 条相互连接的直达公路。
证明：当2)
2)(1(-->
n n m 时，人们便能通
过这些公路在任何两个城市间旅行。
证 用n 个顶点表示n 个城市，顶点间的边表示直达公路，据题意需证这n 个城市的公路网络所构成的图G 是连通的。
反设G 不连通，那么可设G 由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有n 1，n 2个顶点，从而，n = n 1+n 2，n 1 ≥1，n 2 ≥1。
由于各子图的边数不超过2)
1(-i i n n ，因此G 的边数m 满足： ))
1()1((21
)1(2122111-+-=-≤∑=n n n n n n m k i i i
))
1)(1()1)(1((21
21--+--=n n n n
)
2)(1(21
)2)(1(21
21--=-+-=n n n n n
与已知2)2)(1(-->
n n m 矛盾，故图G 是连通的。
14．有7人a ，b ，c ，d ，e ，f ，g 分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。
a 精通英语。
b 精通汉语和英语。
c 精通英语、俄语和意大利语。
d 精通日语和英语。
e 精通德语和意大利语。
f 精通法语、日语和俄语。
g 精通法语和德语。
解 下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言：
由于该图是连通的，因此他们7人是可以自由交谈（必要时借助他人作翻译）。
15．证明：恰有两个奇数度顶点u,v 的无向图G 是连通的,当且仅当在G 上添加边（u ，v ）后所得的图G*是连通的。
证 必要性是显然的。
a
b d
c e g f
设G*是恰有两个奇数度顶点u,v的无向图G添加边（u，v）后所得，且是连通的,那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此G*中删除边（u，v）后所得的图G仍是连通的。
判别图8.31中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。
图8.31
解（a），(b) 是为哈密顿图。
(c) 不是哈密顿图，也没有哈密顿通路。
在图(c)中增加顶点k ，并对其顶点做二着色，构成图(d)（如下）。
图(d) 不是哈密顿图，也没有哈密顿通路。
因为图中白色顶点比黑色顶点多两个。
故(c) 不是哈密顿图，
课后习题:
p279: 1，2，3，5
p287: 3，4，5，7，8
p300: 1，2，3，4
p311: 1，2，3，6
p317: 1，2，4
p321: 1，3，5
p327: 1，2，6
p337: 1，3，6，8。