图论习题

《图论及其应用》习题课教材

目 录

第一章 图的基本概念

1.1 图和简单图 1.2 子图与图的运算 1.3 路与图的连通性 1.4 最短路及其算法

1.5 图的代数表示及其特征 1.6 极图

1.7 交图与团图 习题1

第二章 树

2.1 树的概念与性质 2.2 树的中心与形心 2.3 生成树 2.4 最小生成树 习题2

第三章 图的连通度

3.1 割边、割点和块

3.2 连通度 3.3 应用

3.4 图的宽距离和宽直径 习题3

第四章 欧拉图与哈密尔顿图

4.1 欧拉图

4.2 高效率计算机鼓轮的设计 4.3 中国邮路问题 4.4 哈密尔顿图

4.5 度极大非哈密尔顿图 4.6 旅行售货员问题 4.7 超哈密尔顿图

4.8 E图和H图的联系

4.9 无限图中的欧拉,哈密尔顿问题 习题4

第五章 匹配与因子分解

5.1 匹配

5.2 偶图的匹配与覆盖

5.3 Tutte定理与完美匹配 5.4 因子分解

5.5 最优匹配与匈牙利算法 5.6 匹配在矩阵理论中的应用 习题5

第六章 平面图

6.1 平面图

6.2 一些特殊平面图及平面图的对偶图 6.3 平面图的判定及涉及平面性的不变量 6.4 平面性算法 习题6

第七章 图的着色

7.1 图的边着色 7.2 顶点着色

7.3 与色数有关的几类图 7.4 完美图

7.5 着色的计数，色多项式习题2 7.6 List着色 7.7 全着色 7.8 着色的应用 习题7

第八章Ramsey定理

8.1 独立集和覆盖 8.2 Ramsey定理 8.3 广义Ramsey数 8.4 应用 习题8

习 题 1

1. 证明在n阶连通图中

（1） 至少有n-1条边。

（2） 如果边数大于n-1，则至少有一条闭通道。 （3） 如恰有n-1条边，则至少有一个奇度点。

证明 (1) 若对vV(G),有d(v)2,则：2m=d(v)2n  mnn-1,矛盾！ 若G中有1度顶点，对顶点数n作数学归纳。 当n=2时，G显然至少有一条边，结论成立。 设当n=k时，结论成立，

当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。

(2) 考虑v1v2vn的途径，若该途径是一条路，则长为n-1,但图G的边数大于n-1,因此存在vi,vj,使得viadgvj,这样，vivi+1vj并上vivj构成一条闭通道；若该途径是一条非路，易知，图G有闭通道。

(3) 若不然，对vV(G),有d(v)2,则：2m=d(v)2n  mnn-1,与已知矛盾！ 2. 设G是n阶完全图，试问

（1） 有多少条闭通道？

（2） 包含G中某边e的闭通道有多少？ （3） 任意两点间有多少条路？

答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1.

3. 证明图1-27中的两图不同构：

图1-27

证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4. 证明图1-28中的两图是同构的 图1-28

证明 将图1-28的两图顶点标号为如下的(a)与(b)图

u1 v1

u6 u5 v6 v2 v10 v5 u2 u8 v7 u10 u3 v8 v9 u4 u u 79 v4 v3 (b) (a)

作映射f : f(vi)ui (1 i  10)

容易证明，对vivjE((a)),有f(vivj)uiujE((b)) (1 i  10, 1j 10 ) 由图的同构定义知，图1-27的两个图是同构的。

5. 证明：四个顶点的非同构简单图有11个。

证明

m=0 1 2 3 4 5 6

由于四个顶点的简单图至多6条边，因此上表已经穷举了所有情形，由上表知：四个顶点的非同构简单图有11个。

6. 设G是具有m条边的n阶简单图。证明：m =当且仅当G是完全图。 证明 必要性 若G为非完全图，则 vV(G),有d(v) n-1   d(v)  n(n-1)  2mn(n-1)

n2n m  n(n-1)/2=2, 与已知矛盾！

 充分性 若G为完全图，则 2m= d(v) =n(n-1)  m= 2。

n7. 证明：（1）m(Kl,n) = ln，

n2（2）若G是具有m条边的n阶简单偶图，则m  。

4证明 (1) Kl,n的总度数为2ln,所以，m(Kl,n) = ln。

(2) 设G的两个顶点子集所含顶点数分别为n1与n2,G的边数为m,可建立如下的二 次规划：

m=n1n2 s.t n1+n2=n

n11, n2 1

当n为偶数时，n1=n2=n/2时，m取最大值：m=n2/4

当n为奇数时，取n1=(n+1)/2, n2=(n-1)/2时，m取最大值：m=(n2-1)/4

n2所以，m  。

4

8. 设△和δ是简单图G的最大度和最小度，则δ≤2m / n≤△。

证明

2mnvV2m2md(v)n

nvV2mn2md(v)n

9. 证明：若k正则偶图具有二分类V= V1∪V2，则 | V1| = |V2|。

证明 由于G为k正则偶图，所以，k V1  =m = k V2   V1= V2 。

10. 证明：由两人或更多个人组成的人群中，总有两人在该人群中恰好有相同的朋友数。

证明 将人用图的顶点表示，图的两顶点邻接当且仅当人群中的两人相认识，于是，问题转化为：证明在任意一个简单图中必有一对度数相等的顶点。

若图G为连通单图，则对vV(G),有1d(v)n-1,因此，n个顶点中必存在两个顶点，其度数相同；若G为非连通图，设G1为阶数n1的连通分支，则vV(G1),有1d(v)n1-1，于是在G1中必存在两个顶点，其度数相同。

11. 证明：序列 (7,6,5,4,3,3,2) 和 (6,6,5,4,3,3,1) 不是图序列。

证明 由于7个顶点的简单图的最大度不会超过6，因此序列 (7,6,5,4,3,3,2) 不是图序列；

(6,6,5,4,3,3,1)是图序列  （5，4，3，2，2，0）是图序列，然（5，4，3，2，2，0）不是图序列，所以(6,6,5,4,3,3,1) 不是图序列。

12. 证明：若δ≥2，则G包含圈。

证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G中的路v1v2…vk,若vk与v1邻接，则构成一个圈。若vi1vi2…vin是一条路，由于 2，因此，对vin，存在点vik与之邻接，则vikvinvik构成一个圈 。

13. 证明：若G是简单图且δ≥2，则G包含长至少是δ+1的圈。

证明 设v0v1…vk为G中一条最长路，则v0的邻接顶点一定在该路上，否则，与假设矛盾。现取与v0相邻的脚标最大者，记为l，则l,于是得圈v0v1v2vlv0,该圈长为l+1，显然不小于δ+1。 `

14. G的围长是指G中最短圈的长；若G没有圈，则定义G的围长为无穷大。证明： （1） 围长为4的k的正则图至少有2k个顶点，且恰有2k个顶点的这样的图（在同构意义下）只有一个。

（2） 围长为5的k正则图至少有k2+1个顶点。

证明 (1) 设u,v是G中两相邻顶点，则S(u)S(v)=,否则，可推出G中的围长为3，与已知矛盾。因此，G中至少有2（k-1）+2个顶点，即有2k个顶点。把S(u) v，S(v) u连为完全偶图，则得到2k个顶点的围长为4的图，由作法知，这样的图是唯一的。

(2) 对uV(G),设u的邻接顶点为u1,u2,uk,由于G的围长为5，所以，u1,u2,uk互不邻接。又设ui的邻接顶点为ui1,ui2,uik-1,(i=1,2,…,k),显然，S(ui)S(uj)= u (ij),否则，G

2

中有长为4的圈，所以，G的顶点数至少有k+1个。

15. 对具有m条边的阶n图G，证明：（1）若m≥n，则G包含圈；

（2）若m≥n+4，则G包含两个边不重的圈。

证明 （1）若G含有环或平行边，则G有圈。假定G为n阶简单图。若G中顶点度大于等于2，则G中有圈。设G中有一度顶点，去掉该顶点和其关联的边得图G1,由条件，显然有m(G1) V(G1),若G1中有一度顶点，去掉该顶点和其关联的边得图G2,有m(G2) V(G2),，如此进行下去，该过程不可能进行到n=1或n=2的情形，否则，不满足m≥n

所以，过程进行到Gm,Gm是度数2的图，它含有圈。

(2) 只就m=n+4证明就行了。

设G是满足m=n+4，但不包含两个边不相交的圈的图族中顶点数最少的一个图。可以证明G具有如下两个性质：

1) G的围长g5。事实上，若G的围长4，则在G中除去一个长度4的圈C1的一条边，所得之图记为G,显然，m(G)  V(G)=V(G),由(1),G中存在圈C2, 使C1,C2的边不相交这与假定矛盾；

2） (G)3。事实上，若d(v0)=2,设v0v1,v0v2E(G),作G1=G-v0+v1v2;若d(v0)1,则 G1为在G中除去v0及其关联的边(d(v0)=0,任去G中一条边)所得之图。显然，m(G1)=V(G1)+4,G1仍然不含两个边不重的圈之图。但V(G1)V(G)，与假定矛盾。 由2),n+4=m3n/2  n 8. 但另一方面，由1),在G中存在一个圈Cg，其上的顶点之间的边，除Cg之外，再无其它边，以S0表示Cg上的顶点集，故由2),S0上每个顶点均有伸向Cg外的的边。记与S0距离为1的顶点集为S1，则S0的每一个顶点有伸向S1的边，反过来，S1中的每个顶点仅有唯一的一边与S0相连，不然在G中则含有长不大于g/2+2的圈，这与G的围长为g相矛盾，故S0 S1,于是有：nS0+ S1g+g10,但这与n8矛盾。所以，假定条件下的G不存在。

16. 在图1-13的赋权图中，找出a到所有其它顶点的距离。

v1 1 v4 2 4 9 6 3 a 8 v2 2 v5 6 b 7 2 4 1 2 9 v3 v6

图1-13

解 1. A1= {a}，t(a) = 0，T1 = Φ

2.b1v3

3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)，

T2 ={av3} 2. A2 ={a, v3}, b1(2)(2)v1,b2v2

13. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)，

T3 ={av3, av1} 2. A3 ={a, v3, v1}, b1(3)(3)(3)v2,b2v2,b3v4

3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)，

T4 ={av3, av1, v1v4}

2. A4 = {a, v3, v1, v4}，b1(4) = v2，b2(4) = v2，b3(4) = v2, b4(4) = v5 3. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)，

T5 ={av3, av1, v1v4, v4v5}

2. A5 = {a, v3, v1, v4, v5}，b1(5) = v2，b2(5) = v2，b3(5) = v2 , b4(5) = v2, b5(5) = v2 3. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)，

T6 ={av3, av1, v1v4, v4v5, v4v2}

2. A6 = {a, v3, v1, v4, v5, v2}, b2(6) = v6, b4(6) = b，b5(6) = v6，b6(6) = v6 3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)，

T7 ={av3, av1, v1v4, v4v5, v4v2, v2v6}

2. A7 = {a, v3, v1, v4, v5, v2, v6}, b4(7) = b，b5(7) =b，b7(7) =b 3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)，

T8 ={av3, av1, v1v4, v4v5, v4v2, v2v6, v6b}

于是知a与b的距离

d(a, b) = t(b) = 11

由T8导出的树中a到b路av1v4v2v6b就是最短路。

17. 证明：若G不连通，则G连通。

证明 对u,vV(G),若u与v属于G的不同连通分支，显然u与v在G中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w分别在G中连通，因此，u与v在G中连通。

18. 证明：若e∈E(G)，则ω(G)≤ω(G-e)≤ω(G)+1。

证明 若e为G之割边，则ω(G-e)=ω(G)+1，若e为G之非割边，则ω(G-e)=ω(G)，所以，若e∈E(G)，则ω(G)≤ω(G-e)≤ω(G)+1。

19. 证明：若G连通且G的每个顶点的度均为偶数，则对于任意的v∈V(G)，ω(G-v)

≤d(v)/2成立。

证明 设C为ω(G-v)的一连通分支，则在G中，v有偶数条边伸向C，若不然，C中奇 度点个数为奇数。因此，v至少有两条边伸向C，有ω(G-v)≤d(v)/2成立。

20. 证明：若G的直径大于3，则G的直径小于3。

证明 u,vV(G)，若uvE(G)  uvE(G)dG____(u,v)1。若uvE(G)，则

uvE(G)。分两种情况：(1) 若在V(G)中任意顶点至少和u,v之一相连，在这种情况下，对G中任意两个顶点x,y，有dG(x,y)3，矛盾。

(2) V(G)中存在一点w,使得uw,wv E(G),则uw,wv E(G)，此时，d以，G的直径小于3。

G(u,v)2。所

21．设G是具有m条边的n阶简单图，证明：若G的直径为2且△= n-2，则m≥2n-4。

证明 在G中，设d(v)= △= n-2,与v邻接的顶点设为：v1,v2,…,vn-2,剩下的一个顶点为u, u与v不能邻接。如下图所示。

v u v n-2

v1 vv3 2

由于d(G)=2，因此u与v1,v2,…,vn-2必邻接，否则，G的直径大于2。因此，该图中至少应该有的边数为

n-2+n-2=2n-4,即：m≥2n-4。