湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学

《湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学》由会员分享，可在线阅读，更多相关《湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学（88页珍藏版）》请在装配图网上搜索。

1、习题六 1 .设G是一个无回路的图，求证：若G中任意两个顶点间有惟一的通路，则G是树. 证明：由假设知，G是一个无回路的连通图，故 G是树。 2 .证明：非平凡树的最长通路的起点和终点均为悬挂点. 分析：利用最长通路的性质可证。 证明：设P是树T中的极长通路。若P的起点v满足d(v) >1 ,则P不是T中极长的通路。对 终点u也可同理讨论。故结论成立。 3 .证明：恰有两个悬挂点的树是一条通路. 分析：因为树是连通没有回路的，所以树中至少存在一条通路P。因此只需证明恰有两个 悬挂点的树中的所有的点都在这条通路 P中即可。 证明：设u,v是树T中的两个悬挂点，即d(u) =d(v)

2、 =1。因T是树，所以存在(u,v)-通路 P ： uwi…WkV, k之0。显然，d(Wi)之2。若d(Wi) >2 ,则由T恰有两个悬挂点的假 设，可知T中有回路；若T中还有顶点x不在P中，则存在(u,x)-通路，显然u与x不邻接， 且d(x) ,2。于是, 可推得T中有回路，矛盾。故结论成立。 4 .设G是树，XG心k,求证：G中至少有k个悬挂点. 分析：由于A(G )2k ,所以G中至少存在一个顶点v的度〉k,于是至少有k个顶点与 邻接，又G是树，所以G中没有回路，因此与v邻接的点往外延伸出去的分支中，每个 分支的最后一个顶点必定是一个悬挂点，因此 G中至少有k个悬挂点。 证明

3、：设u WV(G),且d(u)之m之k 。于是，存在v1,…，vm w V(G),使 uvaE(G),i =1,…，m。若Vi不是悬挂点，则有mw V(G),使。如此下去，有m(1Yv(G), 满足vi(l) #vj, i # j,且d(vi⑴)=1, i =1,…，m。故G中至少有k个悬挂点。 5 .设G(p,q谑一个图，求证：若q之p,则G中必含回路. 分析：利用树是没有回路且连通的图，且树中的顶点数和边数的关系可证。 证明：设 G(p, q)有 k 个分支：GM]=G1(p1,q)…，G[Vk] = Gk(Pk,qk)。显然， p = Pi +…+ Pk, q =q[ +…+qk。

4、若G无回路，则每个Gi 2 ,qj均是树，i = 1,…，k。 于是qi = Pi -1, i =1,…，k。从而 q = p—kp-1. 分析：树应该是具有p个顶点中边数最少的连通图，而树中的边数 q=p-1可证。 证明：设G是连通图。若G无

5、回路，则G是树，于是q = p-1。若G有回路，则删去G中 k a0条边使之保持连通且无回路。于是 q -k = p -1, IP q = p-1 +k > p -1o 9 .递推计算K2 3的生成树数目. K2,3 e 10 .通过考虑树中的最长通路，直接验证有标记的5个顶点的树的总数为125. 分析：设树中5个顶点的标记分别为1, 2, 3, 4,

6、 5。而5个顶点的树的最长通路只能是 4、 3、2,如下（1） （2） （3）所示。 （i）。 0 o 0 0最长通路长度为4； （2） q 0 Q q 最长通路长度为 3; O (3) 最长通路长度为2。 对于（1），把每个顶点看作是一个空，不同的顶点序列对应不同的树，但由于对称性12345和54321 所形成的树应该是同一棵树，因此这种情况下所有有标记的树的数目为： 5! /2=60个； 对于（2）,把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一 个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为 4 C5 *4

7、!,但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构 成的数是一样的。因此这种情况下所有有标记的树的数目为： C54 *4! /2=60个； 对于（3）,只要确定了中间度为4的顶点，这棵树就构造完了，所有这种情况下有标记的树的数 目为：C5 =5个； 解：有标记的5个顶点的树的总数为：60+60+5=125个。 11 .用T(n所示n个顶点的有标记树的个数,求证: n _1 2 n -1T n 八 k n - k T k T n - k Ck k 1 由此得恒等式 n 1 k _1 n -k-1 k n _2 k n - k Cn = 2 n

8、-1 n k 4 分析：每个n阶树可由下面的方法构造出来：先从这n个顶点中任取k个顶点构造出一个k阶树， 对剩下的n-k个顶点构造出一个n-k阶树，再将这两个树合并成一个树，显然这样得到的树是一 个n阶的树。又由定理6.2.4有i个顶点的无标记的生成树共有ii-2个，可得下面的证明。 证明：任取k个顶点白一棵k阶树与(n )个顶点构成的n 阶树之间连接两点就是一棵 n阶树， 这里有k (n -k)种连接。并注意到一来一往每条边用了两次，因此，k (n *) T(k) t (n -k)Cnk =2T(n)。 n -1 上式两边对 k从 1 到 nT 求和，得 2(n—1)T(n) =

9、 k(n -k)T(k)T(n -k)C：。再将 T(n) = nn N k=1 T(k) = kk N T (n *)= (n *)n*N代入上式便可得恒等式: n 1 k 1 n4」k n -2 % k (n -k) Cn = 2(n -1)n k 1 12 .如何用Kruskal算法求赋权连通图的权最大的生成树(称为最大树)？ 证明：将Kruskal算法中的“小”改成“大”即可得到“最大树” 13 .设G是一个赋权连通图，V(G ) = "2,…，ntn至2.求证：按下列步骤(Prim算法)可 以得出G的一个最优树. (i )置U :=1,T :=0 ； (ii )选

10、取满足条件i WU, jWV(G )—U且C(i,j垠小的(i, j)； (iii ) T:TU《,j[U :=UU{j}； (iv )若U #V(G )则转(ii ),否则停止,T中的边就是最优树的边. . \ * ，一… … • . * 、一 .. 解：(1)设T是按Prim算法得出的图。由Prim算法的初值及终止条件，可知 T连通，且 * . . . * … * T为G的生成子图。又由(ii)知 T无回路。故T是生成树。 (2)设T(G) ={T |T是G的生成树，T #T },仿定理6.3.1的证明，可证结论成立。 14 .按题13的Prim

11、算法，求出图6. 9的最优树. 解：最优树如下。(权为20) 习题七 1.对图7.7中的两个图，各作出两个顶点割。 (b) 7.7 解： 对图7.7增加加节点标记如下图所示, V11={a,b}； V21={u,v}： V12={c,d} V12={y} 5 2.求图7.7中两个图的K(G刑MG ). 则(a)的两个顶点割为: (b)的两个顶点割为： 解：如上两个图，有 k(G1)=入(G1)=2, k(G2)=1,入(G2)=2 3.试作出一个连通图G ,使之满足：MG )= MG )="G ) 解：做连通图G如下，于是有：k(G) = K(G) =

12、&(G) 4 .求证，若G(p,q诞k -边连通的，则q之kp/2. 证明：设G是k一边连通的，由定义有入(G)呈k.又由定理7.1.2知入(G)三 三入(G)三 2q/ 2q/ 即kw 2q/ ,从而 P q-kp2 17p 一 / p 5 .求证，若G是p阶简单图，且S(G心p-2,则它G)=讥G) 分析：由G是简单图，且d(G )> p-2,可知G中的B (G)只能等于p-1或p-2； 如B(G户p-1,则G是一个完全图,根据书中规定，有 k(G户p-1=B(G); 如B (G户p-2,则从G中任取V (G)的子集V1 ,其中|V1|=3,则V(G)-V

13、1的点导出子图是连 通的，否则在V1中存在一个顶点v,与其他两个顶点都不连通。则在 G中，顶点v最多与 G中其他p-3个顶点邻接，所以d(v)k-3,又根据定义7.1.1,巩G译(G), 有 k(G)=k-2。 证明：因为G是简单图，所以d(v)Wp-1,vCV(G),已知6(G)呈p-2 (i )若 B (G)= p-1,则 G=Kp (完全图)，故 k(G)=p-1= B (G)。 (ii)若B(G户p-2,则GwKp,设u,v不邻接，但对任意的wCV(G),有 u

14、w,vw CE(G).于是，对任意的 V1 JV(G), | V1|=p-3 ,G-V1 必连通. 因此必有 k(G)呈 p-2= B (G),但 k(G)三 B (G)。 故 k(G) = B (G)。 6.找出一个p阶简单图，使$(G)=p—3,但m(G)<6(G) 7 .设G为3 -正则简单图，求证父(G)=MG) 分析：G是一个3 -正则简单图，所以B(G)=3,根据定理7.1.1有m(GE尢(GE&(G),所以 K(G W能等于0, 1, 2, 3这四种情况。下面的证明中分别讨论了这四种情况下 k(G即九(G ) 的关系。 证明：(1)若k(G户0,则G不连通,

15、所以入(G户K(G). (2)设K(G)=1,且u是G中的一个割点，G-u不连通曲于d(u)=3,从而至少存在一个分 支仅一边与u相连，显然这边是G的割边，故入(G)= 1 ,所以入(G户K(G) (3 )设K(G)=2,且｛v1,v2｝为G的一个顶点割。G1=G-v1连通则v2是G1的割点且v2 在G1中的度小于等于3 ,类似于(2)知在G1中存在一割边e2(关联v2)使得G1-e2不连通.另 一方面由于入(G)>=K(G)=2故G-e2连通.由于G1-e2= (G-e2)-v1,故v1是G-e2的割点，且 v1在G-e2中的度小于等于3 ,于是类似于(2)知，在G-e2中存在一割边el

16、,即 (G-e2)-e1=G-｛e1,e2｝不连通,故入(G)=2.所以入(G)=K(G). (4)设 k(G) =3,于是， 有 3 =k (G)三 MG)WB(G)=3，知 k (G)=MG)与 8 .证明：一个图G是2-边连通的当且仅当G的任意两个顶点由至少两条边不重的通路所 连通. 分析：这个题的证明关键是理解2-边连通的定义。 证明：(必要性)因为G是2-边连通的，所以G没有割边。设u, v是G中任意两个顶点， 由G的连通性知u, v之间存在一条路径P1,若还存在从u到v的与P1边不重的路径P2, 设C=P1UP2,则C中含u,v的回路，若从u到v的任意另外路径和P1都有一

17、条(或几条) 公共边，也就是存在边e在从u到v的任何路径中，则从G中删除e, G就不连通了，于是 e成了 G中一割边，矛盾。 (充分性)假设G不是一个2-边连通白1则G中有割边，设e=(u,v)为G中一割边，由已知 条件可知，u与v处于同一简单回路C中，于是e处在C中，因而从G中删除e后G仍然连 通，这与G中无割边矛盾。 9 .举例说明：若在2 -连通图G中，P是一条 (u,u )-通路，则G不一定包含一条与P内部不相 交的(u,u )-通路Q。 解如右图G,易知G是2一连通的， 若取P为uv1v2v, 则G中不存在Q 了。 10 .证明：若G中无长度为偶数的回路,则G的每个块

18、或者是K2,或者是长度为奇数的回 路. 分析：块是G的一个连通的极大不可分子图，按照不可分图的定义，有G的每个块应该是没 有割点的。因此，如果能证明G的某个块如果既不是K2 ,也不是长度为奇数的回路，再由 已知条件G中无长度为偶数的回路，则可得出G的这个块肯定存在割点，则可导出矛盾。本 题使用反证法。 证明：设K是G的一个块，若k既不是K2也不是奇回路，则k至少有三个顶点，且存在 割边e=uv于是u,v中必有一个是割点，此与k是块相矛盾。 11 .证明：不是块的连通图G至少有两个块，其中每个块恰含一个割点. 分析：一个图不是块，按照块的定义，这个图肯定含有割点 v,对图分块的时候也应

19、该以割 点为标准进行，而且分得的块中必定含这个割点，否则所得到的子图一定不是极大不可分子 图，从而不会是一个块。 证明：由块的定义知，若图G不是块且连通，则G有割点，依次在有割点的地方将 G分解 成块，一个割点可分成两块，每个块中含 G中的一个割点。如下图Go 易知u,v是割点，G可分成四个块K1〜K4。其中每个块恰含一个割点。 12.证明：图G中块的数目等于 6(G )+ b (晔)-1) 其中，b(v废示包含u的块的数目. - V G 分析：一个图G的非割点只能分布在G的一个块中，即b(u)=1 (当v是G的非割点时)，且 每个块至少包含一个割点。因此下面就从 G的割点入手

20、进行证明。证明中使用了归纳法 证明：先考虑G是连通的情况(MGH1),对G中的割点数n用归纳法 由于对G的非割点v, b(v)=1 ,即b(v)-1 =0,故对n=0时，G的块数为1 + (bu泊)结论 . V G 成立。 假设G中的割点数n0)时，结论成立。 对门=卜+1的情况，任取G的一个割点a,可将G分解为连通子图G,使得a在Gi中不是割 点，a又是Gi的公共点。这样，每一个 G,有且仅有一个块含有a,若这些G共有「个，则 b(a户r,又显然G的块也是G的块，且Gi的割点数li

21、v)是Gi中含v的块的块数，注意到Gi中异于a的v, :V Gi b(v)= bi(v),而a在每一个Gi中均为非割点，故bi(a)(i=1,2「,r)。于是Gi的块数为 1 % b -1 (i=1,2, ,r) 将所有Gi的块全部加起来，则得到G的块数为: 上:.biu )1 =r -- 期。卜1 =1+(r-1) 一 ;b。,； >-1 =1 -三二垃’；：卜1 v「VG 由归纳法可知，当G连通时，结论成立。 当G不连通时，对每个连通分支上述结论显然成立。 因此有图G中块的数目等于 ，Gr廿 -1 13 .给出一个求图的块的好算法。 分析：设G是一个具有p个顶点，q条

22、边，w个连通分支的图。求图G的块可先求图G的任 一生成森林F,且对每一边e^F,求F+e中的唯一回路，设这些回路 C1, C2,…，Cq-p+w都 已求得，(这些都有好算法)。在此基础上，我们注意到，两个回路(或一个回路与一个块) 若有多于1个公共点，则它们属于同一块。止匕外，由割边的定义知， G的任一割边不含于任 何回路中，且它们都是G的块。基于这些道理，可得如下求图 G的块的好算法。 解： 求图的块的算法： (1) 令 s=1, t=1, n=q-p+w (2)若n>0,输入C1, C2,…，/ 否则，转第4步。 (3)若|V(Cs)CV(Cs+)中,令Cs=Cs=Cs+，且

23、对 i=s+t,…，n-1,令 Ci =Ci由，n =n-1 ,转第4步；否则，t=t+1,转第5步。 (4)若s

24、。设V是一个|V|<2r+1的任 一顶点子集，可分|V叫2r和|V|=2r两种情形证明。 证明： (1)当|V|<2r时，根据定理7.3.1的证明，V’不是H2r,p的顶点割集，当然更不是在 H 2r 0上加些边的H2r 的顶点割集。 A r , p r , p (2)当|V|=2r时，设V是H 2fp的顶点割集，i，j属于H2fp —V的不同分支。考 察顶点集合 S ={i,i 1,..., j -1, j} 和T ={j,j +1,...,i —1,i} 这里加法取模n 若S或T中有一个含V的顶点少于r个，则在H2td -V中存在从i到j的路。与V为 A r , p 顶点

25、割集矛盾。 若S和T中都有V的r个顶点，则： 若S或T中，有一个(不妨说S)中V的r个顶点不是相继连成段，则S-V中存在从 i到j的路。与V为顶点割集矛盾。 若S与T中，V的r个顶点都是相继连成一段的。若S与T中至少有一个没有被分 成两段，则立即与V为顶点割集矛盾；若S-V被分成两段：含i的记S1,含j的记S2 , 且T -V也被分为两段：含i的记T1 ,含j的记T2。这样，V -V被分为两段：含i的 U T1 和含j的S2UT2。这两段都是连通的，且含i段的中间点(或最靠近中间的一点)i0与含j段 的类似点j。满足： jo = * i0 i0 n + — 2 n 1

26、+ 2 (n为偶数) (n为奇数) 故i0与j0有边相连，在 H2r书,p —V中有路(i,...,i0, j0,..., j),与V为顶点割集矛盾。 综上所述，H 2Tp是(2r +1)连通的。 15.证明：K(Hm,n )=MHm,n )= m. 分析：根据定理7.3.1,图Hm,n是m-连通图，因此有 k (Hm,n)=m 又根据Hm,n的构造，可知 6 (Hm,n) 5 ,再由定理7.1.1可证。 证明：由定理7.3.1知：K (Hm,n) =m 已知：k三入三B 而 5 (H m,n) = m.因止匕 m = k M 儿 M 6 = m. 故九(Hm,n)

27、=m. 16.试画出 H48、H58 和 H59 . . ., 分析：根据书上第54页构造H m,n的方法可构造出H48、H58和H59。 . . ., (i) H4.8: r = 2 ,p=8对任意 i,j € V( H4.8), I i- j i—j Er,其中, j =0, j =7,6 J=8,j = 7,6 则H4.8如下图： i = i(mod p), j = j(mod p). 1 =1,j=7 j=9j=7 H 4,8图 (ii) H5.8图：r =2,p=8,则在H 4.8中添加连接顶点 i+p/2(mod p)的边，其中 1

28、5; 2 —6; 3 —7; 4 —0.则 H 5.8 图如下 (iii) H 5.9 图: r=2,在H 4,.9图上添加连接顶点0与 i + (p+1) /2(mod p)的边，其中 1 < i< (p-1) /2和(p+1) /2的边，以及顶点i与 (p-1) /2. i =0, j =8,7 「= 9

29、j = 8,7 :0一4; 0 一5; 一 6； i = 1, j =8 『 二 10， j・ = 8 2 一 7; 3 — 8. 则H5.9图如下: 8 0 7 6 2 3 5 4 H 5,9图 习题8 1、图中8.10中哪些是E图？哪些是半E图? (a) (b) (c) 分析：根据欧拉定理及其推论，E图是不含任何奇点的图，半 E图是最多含两个奇点的图。 解： (a)半E图。(b) E图。 (c)非半E图和E图 2、试作出一个E图G(p,q),使得p与q均为奇数。能否作出一个E图G(p,q),使得p为偶数，而q 为奇数

30、？如果是p为奇数，q为偶数呢？ 解：以下E图中，p与q 的奇偶如下表 P q G1 奇数 奇数 G2 偶数 奇数 G3 奇数 偶数 Gi G2 G3 3、求证：若G是E图，则G 的每个块也是 E图。 分析：一个图如果含有E回路，则该图是E图; 另一方面一个块是G中不含割点的极大连通不可 分子图，且非割点不可能属于两个或两个以上的块。这样沿 G中的一条E回路遍历G的所有边 时，从一个块到达另一个块时，只能经过割点才能实现。 证明：设B是G的块，任取G中一条E回路C,由B中的某一点v出发，沿C前进，C只有经 过G的割点才能离开B,也就

31、是说只有经过同一个割点才能回到 B中，注意到这个事实后，我们 将C中属于B外的一个个闭笔回路除去，最后回到 v时，我们得到的就是B上的一个E回路, 所以B也是E图。 4、求证：若G无奇点，则G中存在边互不重的回路 Ci, ，Cm使得 E(G) =E(Ci) - E(C2)- - E(Cm) 分析：G中无奇点，则除了孤立点后其他所有点的度至少为 2,而孤立点不与任何边关联，因此 在分析由边构成的回路时可以不加考虑；而如果一个图所有的顶点的度至少为 2,则由第五章习 题18知该图必含回路。 证明：将G中孤立点去掉以后得到图 G1,显然G1也是一个无奇点的E图，且"G1)22。由第 五

32、章习题18知，G1必含有回路C1;在图G1-C1中去掉孤立点，得图 G2,显然G2仍然是一个 无奇点的图，且6(G2)及，于是G2中也必含回路C2,…如此直到Gm中有回路Cm,且Gm-Cm 全为孤立点为止，于是有： E(G) =E(G) 一 E&) 一 一 E(Cm) 5、求证：若G有2k>0个奇点，则G中存在k个边互不重的链 Q1… Qk ,使得： 1 , , k E(G) =E(QJ .. E@)「一. E(Qk) 分析：一个图的E回路去掉一条边以后，将得到一条 E链。 证明：设 V1V2,…，Vk,Vk书，…，V2k为G中的奇数度顶点，k> 1在Vi和Vi+k之间用新边ei连

33、 接，i =1, 2….k,所得之图记为G*,易知G*的每个顶点均为偶数，从而 G*存在E闭链C* 。 现从C*中删去ei (i=1, 2….k),则C*被分解成k条不相交的链Qi( i =1, 2….k),显然有： E(G) =E(Q1)一 E(Q2)「一 E(Qk) 6、证明：如果(1) G不是2—连通图，或者(2) G是二分图,且XWY,则G不是H图。 分析：G不是2—连通图，说明MG^1 ,于是工⑸口或K(G)=0 ,如果K(G)=0,则说明g 不连通，如G不连通，显然G不是H图，如K(G)=1则g中存在孤立点，因此有w(G-v)>2, 由定理8.2.1G不是H图。若G是

34、二分图 ,则X或Y中的任意两个顶点不邻接，因此G-X 剩下的是Y中的点，这些点都是孤立点；同样 G-Y剩下的是X中的点，这些点也是孤立点；即 有叫G -X)卡|,8(G —Y) =|X|,如果x.丫，则有0 (G 一X)卡|邓|或s (G -Y)平|>Y|成立。 无论哪个结论成立，根据定理 8.2.1都有G不是H图。 证明：若(1)成立则G不连通或者是G有割点u,若G不连通，则G不是H图，若G有割点u, 取S={u},于是co (G-u)> S因此 G不是H图. 若(2)成立，不妨设|X| <|丫|.令$ = *,则 金(g - S) =|y|>|x| =|s| 即：切

35、(G -S) >|S. 因此G不是H图. (G-S)^S 1. 7、证明:若 G是半H图，则对于V(G)的每一个真子集S,有： 分析：图G的权与它的生成子图 G的连通分支数满足： CO(G)"(G)因为一个图的生成子图 是在该图的基础上去掉若干边得到的，显然去掉边以后只能使该图的连通分支增加。 对于图G的一条H通路C,满足任取Sc V , s(C -S) < S +1. 证明:设C是G的一条H通路，任取SUV,易知 (C -S) < S 1. 而 C-S 是 G-S 的生成子图. 故②(G—S) Wco(C—S)w S+1.故与(G — S)〈S+1. 8、试述H图

36、与E图之间的关系。 分析：H图是指存在一条从某个点出发经过其他顶点有且仅有一次的回路；而 E图是指从某点出 发通过图中所有的边一次且仅有一次的回路。 从定义可看出，这两者之间没有充分或必要的关系。 解：考虑如下四个图： 易知G1是E图，但非H图；G2是H图，但非E图；G3既非E图，又非H图；G4既是E图，也 是H图。 9、作一个图，它的闭包不是完全图 分析：一个p阶图的闭包是指对G中满足d(u)+d(v)> p的顶点u,v,若uv*E(G),则将边uv力口至U G中，得到G+uv,如此反复加边，直到满足d(u)+d(v) >p的所有顶点均邻接。由闭包的定义，如 果一个图本身不存

37、在任何一对顶点 u,v,满足d(u)+d(v)>p,则它的闭包就是其自身。显然可找到 满足这种条件的非完全图。 解：如右图G, G=G,但G不是完全图 10、若G的任何两个顶点均由一条 H通路连接着，则称G是H连通的。 一 一 一，， 一 一 1 (1)证明：若G是H连通的，且p之4,则q之.1(3p+1) 1 一、I (2)对于p皂4,构造一个具有q = J (3p +1)的H连通图Go 2 39 p p 分析：根据定理5.3.1有2q = d(vi),因此q = d(Vi)/2 i 1 i =1 P 而Z d(vi)之P* 6(G),所以q>p*S(G)

38、/2,因此如果能判断S(G)>3,则有 i 4 1 q之pw 6(G)/2至3P/2之『(3p+1)下面的证明关键是判断S(G)>3。 证明：(1)任取we V(G),由于G是连通的，所以d(w)>1o p> 4,所以G H通路与u与 若d(w)=1,则与w邻接的顶点u与w之间不可能有一条H通路连接它们，否则因为 中除了 u与w外还有其他顶点，因此，如果 u与w之间有一条H通路的话，这条 w的连线就构成了一个回路，这样与 d(w)=1矛盾，所以d(w)w1； 同样的道理，若d(w)=2,则与w邻接的顶点u与v之间不存在H通路。 因此 8(G) >3o 从而 2q=Ed(u)>

39、3p, 即：2q>3p,也即 q > 3p/2 1- 八 ⑴若p为奇数，于是 q ^-(3p+1)； 1 (ii)若p为偶数，则3P为偶数，于是 q ^2(3p+1)； 综合以上各种情况，有: 1 q 至 q(3p + 1)； (2) (i )当p=偶数时，q=3p/2,满足条件的图如下图(a); 40 图(a) 11、证明：若G是一个具有p三28的连通简单图，则 G有一条长度至少是2 8的通路。 分析：使用反证法，假设G中没有一条长度大于或等于 2 8的通路。先找到图G的一条最长通路 P,设其长度为m,由假设m<2 8。再在P的基础

40、上构造一条长度为 m+1的回路C,显然C中包 含的顶点数小<2 8,由于p皂28,所以图G至少还有一个顶点v不在该圈中，又由于 G是连通 的，所以v到C上有一条通路P。于是P+C的长度等于通路P的长度的通路构成了一条比 P更 长的通路，这与P是G的一条最长通路矛盾。从而本题可得到证明。 证明：(用反证法)设 p =VV… 栋G的最长通路 淇长度为m,假设m<2 8。 由P是G的最长通路，则V1,Vm+1只3与P中的顶点相邻，注意到 G是简单图 令S ={Vi V2 i E(G)}, T ={Vi vm a E(G)} ,二 S =d (vi)至 6,T =d (vm韦)>5o 由定义

41、知： vm +更S」T ,因止匕|sUT|wmM26 ,于是S^T#中， 事实上，= 2S A SJt = S + T -|s^t|^^ S> - SnT|=2^ - SnT 二怕口丁 卜 0,即 S^TQ。 设丫1三$1丁#我从而有G中的长为 m+1的回路C： v1V2“ivivm41Vm…vi+v1. 因p >26, m+1 W26,所以，C外至少还有一个顶点 v0 e V (G)。 由G连通可知，有一条 P外的通路与C连接。不妨设 v0vj WE (G) ,1EjEm+1. 是有通路P ： V0VjVj 4…V1Vi书…VmVm由ViVi/…V1.且P I A P ,此与P的假

42、设矛盾！ 故结论成立。 12、设p(豺阶简单图G的度序列为：d1Wd2Wrqp.证明：若对任何m, 1 17W(p—1)/2,均有dm>m右p为奇数，还有d1P布与(p—1)则G是H图。 分析：由定理824,如果p (>3)阶简单图G的各顶点度数序列 di京2W」玄p,而且又t任何m

p-m,贝UG是H图。 卜面的证明就是利用这个定理来判断当 m

m。从而G是H图。 证明：对任何正整数 m；E, 2 (1)若p为偶数(p之3),则必有：14mwB—1=E^<_p二1 2 2 2 即1

43、1)/2，由题设有dm >m,再由定理8.2.4知G为H图 (2)若p为奇数，则m E p 1 (a)若m < p 1,则由题设有dm > m, 2 2 p -1 p-1 (b^m= ，地 p—m=p— = 2 2 1 口 r 于是 dp_m =d 1 > ( p -1)Wd p_m 至 (p 1) 2 2 L  2 p - p 1 p 1 2 一 2 1 (p—1)+1 = p — m,也即 dp_m 至 p — m, 2 从而，由定理8.2.4知，G是H图。 13、在图8-8中，如果分别去掉v3, v4和v5,则相应得到的旅行推销员问题的解分别取什么下 界

44、估计值？ 分析：利用Kruskal算法可给出一个关于旅行推销员问题的的下界估计式: 任选赋权完全图Kn的一个顶点v,用Kruskal算法求出Kn-v的最优树T,设C是最优的 H回路，于是有C-v也是Kn-v的一个生成树，因此有：w(T) < w(C-v) 设e1和e2是Kn中与v关联的边中权最小的两条边，于是： w(T)+w(e1)+w(e2)

45、+9=35, (2 )去掉 v4 后，仿上有 w(T4)=20, w(C4)=20+7+8=35; (3)去掉 v5 后，有 w(T5)=26, w(C5)=26+1+5=32. 14、设G是一种赋权完全图，其中对任意 x,y,zC V(G),都满足缶 仅十8 &Z " 仅才： 证明：G中最优H回路最多具有权 28(T)其中T是G中的一棵最优树。 分析：H回路是指从图中某点出发，经过图中每个顶点有且仅有一次，最后回到出发点的一条回 路。由于G是一种赋权完全图，所以从任意顶点出发包括了 G的其他所有顶点有且仅有一次再回 到原点的回路都构成了 G的一条H回路C,且最优H回路C的权满足

46、。因此只 42 8(C)%(C) E(O<2(T) 需证明G中存在一条H回路C,其权 即可，因此证明本题的关键是找到满足这 个结论的H回路C。 证明：设T是G中的一棵最优树，将T的每边加倍得到图T,则T的每个顶点的度数均为偶数。 所以T有一欧拉回路Q,设Q=(v1, v2，…，vn,v1), (n>|v(G)|), Q中某些顶点可能有重复， 且 0 (Q)=28(T) 在Q中，从v3开始，凡前面出现过的顶点全部删去，得到 G的|v(G)由顶点的一个排列兀。由 于G是完全的，所以兀可以看作G中的一个H回路。在兀中任意边(u,v),在T中对应存在唯一 的(u,v)-通路P,由权的三

47、角不等式有 切(u,v))由于将兀中的边(u,v)用T中的P来代替时，就得到Q,因而 (冗)抬(Q)=2o(T澈G中的最优H回路C的权 切(C)

48、。于是 Mi份M2 #中。易知边导出子图H =T[Mi M2]中的每个顶点v满足dH(v) A 2。于是H 中存在回路，从而T中有回路。此与T是树矛盾，故结论成立。 2 .证明：树G有完美匹配当且仅当对任意 vWV(G),均有O(G—v) = 1 分析：一方面，由定理9.1.3图G存在完美匹配当且仅当对任意 SUV(G),有O(G—S)E|S|,所 以如果树G有完美匹配，则O(G-v)4v}|=1 ；而G有完美匹配，说明|V(G) =偶数，所以 O(G -v)之 1 ；从而有 O(G -v) =1。 另一方面，如果对任意v^V(G),均有O(G -v) =1 ,则对v而言，可利用这个这

49、个奇分 支找到v关联的唯一边，从而构造出 G的一个完美匹配。 证明：必要性 设G有完美匹配。 由定理9.1.3,取S ={v},则 O(G -v) =O(G -S) M|S| = 1 又•「G有完美匹配，|V(G)上偶数。于是M(G—v)|=奇数。 故 O(G—v)*.从而 O(G—v)=1. 充分性 设对任意v ^V(G),有O(G —v) =1. 即G —v恰有一个奇分支Co(v),因G是树，故v只能与Co(v)中的一个顶点邻接。设v与Co(v) 的关联边为e(v)KuWE(G)。显然v确定以后，uv是唯一确定的，且易知Co(u)=uv。因为G-v 只有一个奇分支Co(v),

50、则G-u以后，v应该与G-v的其他偶分支在一个连通分支中，而这个分 支的顶点数显然是奇数，从而构成G-u的唯一一个奇分支Co(u),而u与这个奇分支中的顶点显 然也只有与v邻接，所以Co(u)=uv。于是对任意vW(G),按这样的方法构造其关联边 e(v), 所的的匹配 M ={e(v) |v WV(G)}就是G的一个完美匹配 3 .设k >1是奇数。举出没有完美匹配的k -正则简单图的例子。 分析：作G如下：取2k-1个顶点v1,2」’,v2ki,在奇足标顶点和偶足标顶点间两两连以边外， 再连以V1V3,V5v7： ,V2k_5V2k工边，所得图记为G0,显然G0除V2k」外其余顶点的

51、度均为k,而V2k」 的度为k-1,取k个两两不相交的Go的拷贝和一个新顶点V0,并把每个Go拷贝中对应于V2k」的 顶点与Vo相连以边。最后所得的图记为G,显然G是k-正则的简单图。又由于Go含2k-1个顶点， 则G的顶点数为：k*(2k-1)+1。所以如果G有一个完美匹配M的话，则 k*(2k-1) 1 , 2 k-1 |M|= -- = k 。 2 2 假设M是G的一个完美匹配，则其边应来自 k个独立的Go,和跟Vo相关联的一条边。 而每个Go,其包含的顶点数为2k-1,所以Go能提供给M的边最多为k-1条，k个这样的Go能提 2 2 k-1 供给M的边最多为k*(

52、k-1),因此M最多包含的边为k*(k-1)+1=k 2-(k-1)< k ——,因此G不可 2 能有完美匹配。 解：令k=3,得到的图Go及G如下： 4 .设k A o为偶数，举出没有完美匹配的 k-正则简单图的例子. 分析：当k为偶数时，取G=Kk+1,则G的顶点数为k+1 ,显然G的顶点数为奇数，所以G无完 美匹配。 解：令k=2时，可构造出无完美匹配的 2-正则图K3 o 5 .两人在图G上进行对奕双方分别执黑子和白子，轮流向 G的不同顶点Vo,Vi,V2,… 下子，要 求当i >0时，Vi与v」邻接，并规定最后可下子的一方获胜。若规定执黑子者先下子，试证明执

53、 黑子的一方有取胜的策略当且仅当 G无完美匹配。 分析：假设G有完美匹配，则G的每个顶点都是M-饱和点，这样先下者无论取哪个顶点，后下 者都可取其相邻的M-饱和点，这样先下的人必输；因此先下的人如要赢的话，G中肯定无完美匹 配。 反过来，如果G中无完美匹配，由于任何图都有最大匹配，则可找到 G的一个最大匹配 M,由 于M不是完美匹配，因此 G中存在M-非饱和点v,先下的黑方就可找到这个点下，则与 v相邻 的下一个点必是M-饱和点，不然，M U{uv}就是一个更大的匹配，与M是最大匹配矛盾。同理G 中不存在M可增广路，故黑方所选vi必是M饱和点，如此下去，最后必是白方无子可下，故黑 方必胜。

54、 证明：必要性(反证法) 若G中存在一个完美匹配M ,则G中任何点v都是M饱和点。 故不论执黑子(先下者)一方如何取 v一,白方总可以取M中和v^关联边的另一端点作为M , 于是，黑方必输。 充分性.设G中不存在完美匹配，令M是G的最大匹配，而v0是非M饱和点。于是，黑方 可先取v0点，白方所选必必是M饱和点(因M是最大的匹配)由M的最大性可知G中不存 在M可增广路，故黑方所选m必是M饱和点，如此下去，最后必是白方无子可下，故黑方必胜。 6 .证明：二分图G有完美匹配当且仅当对任何 S v(G),有 |s.|Ng(s)| 成立 举例说明若G不是二分图，则上述条件未必充分。 分析：由

55、定理9.1.2Hall定理，对于具有二划分(X,Y)的二分图，G有饱和X中每个顶点的匹配 当且仅当对任意的SX ,<|S|<|Ng(S),显然如果G有完美匹配M的话，则M既饱和X, 也饱和Y。但当G不是二分图时，这个结论不一定成立，如 K2n+1对任意的S=V(G)满足 |S闫Ng(S)|,但它无完美匹配。 证明：必要性.设G有完美匹配M ,则M饱和X及Y ,由Hall定理和对任何S X或 SY ,有 |S|-|Ng(s)| 今任取S=V(G),有$ = & = $2,& =X, S21Y于是有 |S|=|S - S2|=|S| |S|-|Ng(S)| |Ng(S2)| 二|Ng(S

56、i - S2)|=|Ng(S)| 46 充分性：设对任何S 3 V (G),有| S凶Ng (S)|. 即任取SIX ,有|S区Ng(S)|,于是由Hall定理，存在饱和X的匹配M(X),同理，存 在饱和Y的匹配M (Y),从而| X |二|Y |,易知M (X)和M (Y)都是完美匹配。 当G不是二分图时，条件不充分，如 G = K3。 7 . 2n个学生做化学实验，每两个人一组，如果每对学生只在一起互作一次实验，试作出一个安 排，使任意两个学生都在一起做过实验。 分析：该题可转化为对具有2n个顶点(可分别记为0, 1, 2,…，2n-1)的完全图构造其不同的 2n-1

57、个完美匹配，使得(0, 1) (0, 2)…(0, 2n-1), (1, 2) (1, 3),…，(1, 2n-1)…， (2n-2,2n-1)在这2n-1个匹配中出现且仅出现一次。 解： 共安排2n-1次实验，可使任意两个学生都在一起做过实验。安排如下： 第 1 次：(0,1), (2, 2n-1), (3, 2n-2),……,(x,y)其中,x+y=2n+1; 第 2 次：(0, 2), (3, 1), (4, 2n-1),……,(x, y) 其中，x+y=2n+3; 第 2n-1 次：(0, 2n-1), (1,2n-2), (2, 2n3),……,(x, y)其中，x+y=2n

58、-1; 8 .试证明：任何一个(0,1)矩阵中，包含元素1的行或列的最小数目，等于位于不同行不同列 的1的最大数目。 分析：由定理922,对二分图G,均成立a (G) = P(G)(其中a,(G)为G的最大匹配数，P(G) 为G的点覆盖数)。将给定的(0, 1)矩阵表示成一个二分图G(V1,V2,E) V1 ={U1,…，un} , V2 ={V1,…，vn}.其中 M(i, j) =1 当且仅当(u,Vj)w E(G) 该题转化为了判断G的0(G)和a (G)的关系。 证明： 设M m>n是一个(0,1)矩阵.将M m沏表示成一个二分图G(V1,V2 ,E), V1 ={u1,…，

59、Un} , V2 ={必,…，Vn} .其中 M(i, j) =1 当且仅当(Ui,Vj)w E(G) 于是，G的(最小)点覆盖数P(G)等于含M m看中元素1的行(第i行元素1的数目表示顶点ui 覆盖的边之数目)或列(第j列元素1的数目表示顶点Vj覆盖的边数目)的数目。而 G的最大 匹配数a (G)等于M m坨中位于不同行不同列的1的最大数目. 由定理9.2.2知，若G为二分图，则a(G) = P(G)。故结论成立. 9 .能否用5个1父2的长方表将图9-13中的10个1父1正方形完全遮盖住？ 图 9-13 分析：按如下方法作出G图：在图9-13的每个正方形格子中放一个顶点，U与

60、V邻接当且仅当U 与V所在的方格有公共边。则该问题等价于判断相应图 G是否有完美匹配， 解：按照分析，构造图G如下：则有O(G1={u}|,由定理9.1.3可判断它没有完美匹 配。因此不能用5个1父2的长方表将图9-13中的10个1父1正方形完全遮盖住。 1 10 .试证明：G是二分图当且仅当对 G的每个子图H均有 a(H ) >- |V(H) |o 2 分析：若6= (X,Y)是二分图，显然X和Y都构成G的点独立集，所以G的最大独立数ct(G)>|X| , 且u(G)平|;而二分图的每个子图显然也是二分图。 证明：必要性.设G是二分图，于是 G的任何子图 H也是二

61、分图，设 H =(X,Y), |X | 十|Y|=|V(H)|。不妨设 |X 户|丫|。显然 (H) >| X |,因此， 次⑼之必mX|+|Y田⑼|。于是，a(H)却V(H)1。 充分性.若G不是二分图，则G中含奇回路C。令H =C。显然， a(H ) = V(H)/2」工工|V(H)|。矛盾。故G 是二分图。 48 11 .试证明：G是二分图当且仅当对 G的每个适合6(H ) >0的子图H ,均有a(H) = P(H). 分析：ot(G)是指G的最大独立集，P

62、,因此如果能证明 P,(H )=max(|X|,|Y|),则对不含孤立点的二分图 G,有a(G)=P，(G) 证明：必要性.设G是二分图。 HWG, 6(H) >0 ,即H无孤立点。显然H也是二分图， 设H =(X,Y),且| X以丫 |。于是， u(H ) =|X |。而一条边最多覆盖一个顶点，故 pH) >|X |o 但由于 H 无孤立点，因此，P(H) <|X| ,故 P(H )=|X | = u(H)。 充分性.若G不是二分图，则G含奇回路C = H。设|V(H)|=2n+1, n之1。于是 a(H) =n ,而 P(H) =n +1 >s(H)。矛盾。故 G 必为二分图。 1

63、2 .设G是具有划分(X, Y)的二分图。证明：若对于任何 uw X,vWY.均有d(u)之d(v), 则G有饱和X中每一顶点的匹配。 分析：根据定理9.1.2,二分图G有饱和X中每个点的匹配当且仅当对任何 S= X，有|S四Ng(S)| 根据这个结论，如果能说明满足条件的二分图 G中不存在任何SG X ,有|S|>|Ng(S)| ,则题目 得证。 证明：由题意知，对VuWX, d(u)之1。 若G中不存在饱和X的匹配，则由Hall定理，存在S= X ,使|S|>| Ng(S)|。 设 S={u1 J ,um}, Ng (S) ={Vj …，％ },其中 m > n o 1 , n

64、 由对任何uWX,vWY, d(u)之d(v),得 d(u)至d d(v),但由于S中的点关联的边 u S v三Ng (S) 都是Ng (S)的点关联的边，因此d d(u)< d d(v),因此有 d(u)= d d(v),但m〉n, u S v=Ng (S) u S v三Ng(S) 因此在Ng (S)中总存在一点，有d(vjr)>d(ut)。矛盾。故G中存在饱和X的匹配。 13.证明(Hall定理的推广)：在以G(X,Y)为二划分的二分图G中，最大匹配数二(G)为 「(G) =min{| X -S| |Ng(s)|} s x - 分析：由定理9.2.2有：如果一个图G是二分图

65、，则u(G) = P(G) , a(a)是G的最大匹配数， P(G)是G的最小覆盖。因此如果能说明 mjn{|X-S|[Ng(S)|}等于目(G)的话，则本题得以 证明。 s x 证明：由于{X —S}「Ng(S)H,所以 |X—S|+|Ng(S)| = {X—S}j{Ng(S)}| 显然{ X —S}3{Ng (S)}是G的一个覆盖，而G的任意一个覆盖都可以写成{ X —S}={ N g (S)}的 形式，所以 FG) = min{|X-S| |Ng(S)|} 因此有：(G) = -(G)=xmin{|X-S| |Ng(S)|} S x 49 14 .证明：在无孤立点的二

66、分图 G中，最大独立集的顶点集“(G)等于最小边覆盖数P (H)。 证明：参见题11 15 .在9个人的人群中，假设有一个人认识另外两个人，有两个人每人认识另外 4个人，有4个 人认识另外5个人，余下的两个人每人认识另外的 6个人。证明：有3个人，他们全部互相 认识。 分析：将该题中的人用图中的节点表示，两个节点有连线当且仅当两个人认识，则该题转化为求 证满足上述条件的图G含有一个K3。 要判断一个图是否含有 K3,我们先要了解以下概念和定理： T2, p：具有p个顶点的完全2分图，如果p是偶数，则该图的每一部分顶点数为 p/2;如果p为奇 数，则该图的其中一部分顶点数为(p-1)/2,另一部分顶点数为(p+1)/2。 Turan定理(托兰定理)的推论：若简单图 G不含K3,则E(G)< E(T2,p),且当E(G)=E(T2,p)时， 有G三T2, p 该定理的严格内容为：若简单图G不含Km+1,则E(G)WE(Tm，p)