第9章 习题解答
习题 9.3
1.有向图G如图9.20所示。 ⑴求a到d的最短路和距离。 ⑵求d到a的最短路和距离。
⑶判断G是哪类连通图，是强连通的？是单向(侧)连通的？还是弱连通的？ ⑷将有向图G略去方向得到无向图G?，对无向图G?讨论(1)，(2)两个问题。
解：⑴a到d的最短路为：aed，距离为d?a,d?=2。 ⑵d到a的最短路为deba 距离为d?d,a?=3。 ⑶G是单向连通的和弱连通的，但不是强连通的。 ⑷a到d的最短路为aed 距离为d(a,d)=2。 d到a的最短路为dea 距离为d(d,a)=2。
2.图9.21是有向图，试求该图的强分图，单向(侧)分图和弱分图。
解：结点集?1,2,3?导出子图是该图强分图；结点集?1,2,3,4,5,6?导出子图是该图的单向分图和弱分图，即该图是它自己的单向分图和弱分图。
3.G为无向连通图，有n个结点，m条边，证明m≥n–1。对有向图，这个结论对吗? 证明：对m归纳证明。
当m=0时，由于G是连通图，所以它必为平凡图，n=1，n-1≤m。 设m=k-1时，结论成立。下证m=k时，结论也成立。
从G中删除一条边得G′, G′可能是连通的，也可能是不连通的。
6
第9章 习题解答
⑴当G′是连通图时，G′有n个结点，k-1条边，由归纳假设n–1≤k-1＜k=m，即n–1≤m。
⑵当G′是不连通图时，G′有n个结点，k-1条边，设有2个连通分支，分别为：G1=?V1, E1?和G2=?V2, E2?。| V1|+| V2|=n，| E1|+| E2|= k-1。
由归纳假设有| Vi|－1≤| Ei|，i=1,2。
| V1|+| V2|-2≤| E1|+| E2|，n–2≤k-1，n–1≤k=m，即n–1≤m。 因为强连通图和单向连通图都是弱连通的，所以这个结论也是成立的。
4.设G=?V,E?是一个简单图，|V|≤2n，?v?V，deg(v)≥n，证明G是连通图。若|V|≤2n，?v?V，deg(v)≥n–1，那么，G是连通图吗? 为什么?
证明：(1)先证，?v,u?V，deg(v)+ deg(u)≥|V|-1时，简单图G=?V,E?是连通图。 反证法，设简单图G=?V,E?不是连通图，至少有两个连通分支，设为G1=?V1,E1?，G2=?V2,E2?。?v?V1，因为G1是简单图，deg(v)≤|V1|-1，同理，?u?V2，deg(u)≤|V2|-1，deg(v)+ deg(u)≤|V1|+|V2|-2=|V|-2＜|V|-1。与条件矛盾。所以，简单图G=?V,E?是连通图。
(2)再证，|V|≤2n，?v?V，deg(v)≥n时，G是连通图。
?v,u?V，deg(v)+ deg(u)≥2n≥|V|≥|V|-1，由(1)，G是连通图。
(3)若|V|≤2n，?v?V，deg(v)≥n–1时，此结论不成立。请看反例。令n=1，|V|≤2，?v?V，deg(v)≥0，两个孤立点构成的零图满足此情况，但这样的图是不连通图。
5.证明：若图G是不连通的，则G的补图G是连通的。
证明:因为 G=?V,E?不连通,故G至少有两个连通分支,设为G1=?V1,E1?和G2=?V2,E2?, ?v,u∈V，有下列三种情况：
①u∈V1，v∈V2 (或u∈V2，v∈V1)
在G中，因为v，u来自不同的连通分支，所以，它们之间间无边。因而，在G中，v，u之间必有边。
②u∈V1，v∈V1。
?w∈V2，在G中，u和w之间有边且 v和w之间也有边，于是通过w，v与u之间有路。
③u∈V2，v∈V2。 可类似②证明之。
6.设G=?V,E?是一个简单图，|V|=n，|E|=m， m＞
1(n—1)(n—2)。证明G是连通的。 2证明：反证法。假设G=?V,E?不连通，不妨设G可分成两个连通分支，G1=?V1,E1?和G2=?V2,E2?。则| V1|= n1，| E1|= m1，| V2|=n2，| E2|= m2。
由于n1≥1和n2≥1，有n2≤n-1和n1≤n-1
从而 |E|=| E1|+| E2|≤ ＝
1111n1(n1-1)＋n2 (n2-1)≤(n-1)(n1-1)＋(n-1)(n2-1) 222211(n-1)(n1＋n2-2)=(n-1)(n -2) 227
第9章 习题解答
这与假设矛盾。所以G是连通图。
7.证明：图G的一条边e不包含在G的回路中当且仅当e是G的割边。 证明: 设G的一条边e不包含在G的回路中，以下证明e是G的割边。
删除e，至少连接e的两个结点不连通。所以，图不连通，则e是G的割边。 设e是G的割边，证明e不包含在G的回路中。
反证法，如果e包含在G的某个回路中，删除e，图仍连通，与e是G的割边矛盾。 所以命题成立。
8.令G是一个至少有三个结点的连通图，下列命题是等价的。 ⑴G没有桥。
⑵G的每二个结点在一条公共的简单回路上。
⑶G的每一个结点和一条边在一条公共的简单回路上。 ⑷G的每二条边在一条公共的简单回路上。
⑸对G的每一对结点和每一条边，有一条联结这两个结点而且含有这条边的简单路。 ⑹对G的每一对结点和每一条边，有一条联结这两个结点而不含有这条边的基本路。 ⑺对每三个结点，有一条联结任何两个结点而且含第三个结点的简单路。 证明：(1)?(2)
令u,v是G中任意两个结点，下面对u,v的距离d(u,v)作归纳证明。
①当d(u,v)=1，因为G中没有桥，(u,v)不是桥，G又是连通图，所以，必有一条回路包含(u,v)，所以u,v在一个公共的简单回路上。
②假设当d(u,v)=k时(k≥2)，命题成立。考察一条长为k的u到v的一条基本路。设w是这条路上结点v前面的那个结点，d(u,w)=k-1，由归纳假设u，w两个结点必在G的某个简单回路上。该回路由P1，P2组成，如图9.80(a)所示。因为G中无桥，所以G-(v,w)=G′(从G中删除边(v,w))必仍是连通图。因此，u与v之间必有一条不包含(v,w)的简单路P′。P′与P1，P2间的关系如图9.80 (a)(b)(c)所示的三种情况。
设x是P′上与v最近且在P1或P2上的交点，不妨设x在P1上，如图9.80(a)所示。则以P1上的u到x段，续以P′上的x到v段为?1，以P2上u到w段，续以边(w,v)为?2，则
?1与?2就构成了G中一条通过u,v的公共简单回路，其它两种情况，如图9.80(b)(c)所示，
证法类似。
8
第9章 习题解答
(2)?(3)
设u为G中的任意一结点，e为G中任意一边，令e=(v,w),由(2)可知u,v在公共简单回路Z上，若w?Z，则e?Z，（3）成立。
若w?Z，设P1，P2为两条不同的u到v的简单路，设v, w所在的简单回路为Z′。令P′= Z′-{e}为v到w不含e的简单路，如图9.81所示，令u′是P′上与P1或P2上的最后一个交点，不妨u′在P1上，则以P1的u到u′段，续以P′上的u′到w为?1，以P2续以e =(v,w)为?2，则?1与?2组成了一个简单回路，包含u和e，所以(3)成立。
当u′=v时，证明是类似的。
(3)?(4)
设e1，e2为G中任意两条边， e1=(u1,v1)，e2=(u2,v2)，由(3)知u1和e2在公共的简单回路Z上，若v1?Z，则e1?Z，故(4)成立。
若v1?Z，由(3)可知v1和e2也在一个公共简单回路Z′上。Z与Z′有图9.82 (a)(b)(c)(d)(e)各种情况。
设P1为Z上u1到v2上的一段简单路(不含u2)，P2为Z上u1到u2的一段简单路(不含v2)，P′为Z′上v1到v2的一段简单路(不含u2)。再设u′为P′上与P1或P2的最先一个交点(如图9.82(b)所示)，则以P′上的v1到u′段，续以P1的u′到v2为?1，以e1续以P2，再续以e2为?2，则?1与?2组成包含的e1，e2简单回路，其余情况证法类似。
9
第9章 习题解答
所以，(3)?(4) (4)?(5)
设u,v为G中任意两结点，e为G的任意边，若u,v邻接，则由(4)必有一条公共简单回路包含结点u,v和边e。
若u,v不邻接，由G连通，对结点u必有邻接边e′=(u,s)，故e, e′必在同一简单回路上，设该简单回路为Z。
①若v?Z，则命题成立。
②若v?Z，因为G连通，故v与Z中每个结点至少有一条路，故也有一条简单路。 设w是Z上离v最近的点，P为v到w的最短简单路，以Z中含有e的u到w的简单路，续以P，即构成u到v含有e的简单路，如图9.83(a)所示。
当w=u时，情况类似。如图9.83(b)所示。 故(4)?(5)成立。 (5)?(7)
设u，v，w为G中任意三点，因为G连通，故G中必有关联w的边e，由题设，u,v, e在一个简单回路上。即有一条以u,v为端点，且包含e的简单路，即(7)成立。
(7)?(1)：用反证法。 若G中至少有一个桥，设为e，则G-?e?为不连通图，又G是至少三个结点的连通图，故在G中删除一边后，至少有一个连通分支含有两个或两个以上的结点。若不然，G-?e?中至少有三个以上孤立结点，则加上任何一条边，G不可能为连通图，与题设矛盾。
设u,v为G-?e?的同一连通分支两个结点，令w为不属于该连通分支的G的另一个结点，因为G-?e?为不连通图，故w必存在，在这样的G中，必不可能存在一条u到v的且含有w的简单路。因为，若这样的简单路存在，则删除这条简单任一边，w仍与u或v中至少存在一条路，故w属于u,v所在连通分支中，与假设矛盾。
所以(7)?(1)。 (1)?(6) 反正法。
设G为至少三个结点的连通图，且G无桥。u，v为G中任意两个结点，且G中所有u，v之间的基本路均含有某条边e，则G-?e?中u，v必不连通，所以e为桥，与题设矛盾。于是对G中任意两个结点和任意一条边，G中必有连接这两个结点，但不含这条边的一条基本路，即(1)?(6)成立。
(6)?(1)
10