资源描述
习题六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) =1。因T是树，所以存在(u,v)-通路P ： uwiWkV, 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个悬挂点。证明：设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)，GVk = Gk(Pk,qk)。显然， p = Pi + Pk, q =q +qk。若G无回路，则每个Gi 2 ,qj均是树，i = 1,，k。 于是qi = Pi -1, i =1,，k。从而 q = pkp, k21,即qp-1.分析：树应该是具有p个顶点中边数最少的连通图，而树中的边数 q=p-1可证。证明：设G是连通图。若G无回路，则G是树，于是q = p-1。若G有回路，则删去G中 k a0条边使之保持连通且无回路。于是 q -k = p -1, IP q = p-1 +k p -1o9 .递推计算K2 3的生成树数目.K2,3e10 .通过考虑树中的最长通路，直接验证有标记的5个顶点的树的总数为125.分析：设树中5个顶点的标记分别为1, 2, 3, 4, 5。而5个顶点的树的最长通路只能是 4、 3、2,如下（1） （2） （3）所示。（i）。0 o 00最长通路长度为4；（2） q0Qq最长通路长度为 3;O(3)最长通路长度为2。对于（1），把每个顶点看作是一个空，不同的顶点序列对应不同的树，但由于对称性12345和54321所形成的树应该是同一棵树，因此这种情况下所有有标记的树的数目为：5! /2=60个；对于（2）,把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为4C5 *4!,但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构成的数是一样的。因此这种情况下所有有标记的树的数目为：C54 *4! /2=60个；对于（3）,只要确定了中间度为4的顶点，这棵树就构造完了，所有这种情况下有标记的树的数目为：C5 =5个；解：有标记的5个顶点的树的总数为：60+60+5=125个。11 .用T(n所示n个顶点的有标记树的个数,求证:n _12 n -1T n 八 k n - k T k T n - k Ck k 1由此得恒等式n 1 k _1n -k-1 kn _2k n - k Cn = 2 n -1 nk 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(n1)T(n) = k(n -k)T(k)T(n -k)C：。再将 T(n) = nn N k=1T(k) = kk N T (n *)= (n *)n*N代入上式便可得恒等式:n 1 k 1n4kn -2% k (n -k) Cn = 2(n -1)n k 112 .如何用Kruskal算法求赋权连通图的权最大的生成树(称为最大树)？证明：将Kruskal算法中的“小”改成“大”即可得到“最大树”13 .设G是一个赋权连通图，V(G ) = 2,，ntn至2.求证：按下列步骤(Prim算法)可以得出G的一个最优树.(i )置U :=1,T :=0 ；(ii )选取满足条件i WU, jWV(G )U且C(i,j垠小的(i, j)；(iii ) T:TU,jU :=UUj；(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算法，求出图6. 9的最优树.解：最优树如下。(权为20)习题七1.对图7.7中的两个图，各作出两个顶点割。(b)7.7解： 对图7.7增加加节点标记如下图所示,V11=a,b；V21=u,v：V12=c,dV12=y52.求图7.7中两个图的K(G刑MG ).则(a)的两个顶点割为: (b)的两个顶点割为：解：如上两个图，有 k(G1)=入(G1)=2, k(G2)=1,入(G2)=23.试作出一个连通图G ,使之满足：MG )= MG )=G ) 解：做连通图G如下，于是有：k(G) = K(G) =&(G)4 .求证，若G(p,q诞k -边连通的，则q之kp/2.证明：设G是k一边连通的，由定义有入(G)呈k.又由定理7.1.2知入(G)三三入(G)三2q/2q/即kw 2q/,从而Pq-kp217p 一/ p5 .求证，若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)-V1的点导出子图是连 通的，否则在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),有uw,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)=p3,但m(G)=K(G)=2故G-e2连通.由于G1-e2= (G-e2)-v1,故v1是G-e2的割点，且 v1在G-e2中的度小于等于3 ,于是类似于(2)知，在G-e2中存在一割边el,即 (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都有一条(或几条) 公共边，也就是存在边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的每个块或者是K2,或者是长度为奇数的回路.分析：块是G的一个连通的极大不可分子图，按照不可分图的定义，有G的每个块应该是没 有割点的。因此，如果能证明G的某个块如果既不是K2 ,也不是长度为奇数的回路，再由 已知条件G中无长度为偶数的回路，则可得出G的这个块肯定存在割点，则可导出矛盾。本 题使用反证法。证明：设K是G的一个块，若k既不是K2也不是奇回路，则k至少有三个顶点，且存在 割边e=uv于是u,v中必有一个是割点，此与k是块相矛盾。11 .证明：不是块的连通图G至少有两个块，其中每个块恰含一个割点.分析：一个图不是块，按照块的定义，这个图肯定含有割点 v,对图分块的时候也应该以割 点为标准进行，而且分得的块中必定含这个割点，否则所得到的子图一定不是极大不可分子 图，从而不会是一个块。证明：由块的定义知，若图G不是块且连通，则G有割点，依次在有割点的地方将 G分解 成块，一个割点可分成两块，每个块中含 G中的一个割点。如下图Go易知u,v是割点，G可分成四个块K1K4。其中每个块恰含一个割点。12.证明：图G中块的数目等于6(G )+ b (晔)-1)其中，b(v废示包含u的块的数目.- V G分析：一个图G的非割点只能分布在G的一个块中，即b(u)=1 (当v是G的非割点时)，且 每个块至少包含一个割点。因此下面就从 G的割点入手进行证明。证明中使用了归纳法证明：先考虑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-1 =1 -三二垃；：卜1vVG由归纳法可知，当G连通时，结论成立。当G不连通时，对每个连通分支上述结论显然成立。因此有图G中块的数目等于，Gr廿 -113 .给出一个求图的块的好算法。分析：设G是一个具有p个顶点，q条边，w个连通分支的图。求图G的块可先求图G的任 一生成森林F,且对每一边eF,求F+e中的唯一回路，设这些回路 C1, C2,，Cq-p+w都 已求得，(这些都有好算法)。在此基础上，我们注意到，两个回路(或一个回路与一个块)若有多于1个公共点，则它们属于同一块。止匕外，由割边的定义知，G的任一割边不含于任何回路中，且它们都是G的块。基于这些道理，可得如下求图 G的块的好算法。解：求图的块的算法：(1) 令 s=1, t=1, n=q-p+w(2)若n0,输入C1, C2,，/ 否则，转第4步。(3)若|V(Cs)CV(Cs+)中,令Cs=Cs=Cs+，且对 i=s+t,，n-1,令Ci =Ci由，n =n-1 ,转第4步；否则，t=t+1,转第5步。(4)若sn,令t=1,转第3步；否则，算法停止(这时 C1, C2,，Cn与E (G) - C1 ,C2,，Cn中的每一边都是G的块)(5)若s+tn转第3步；否则，s=s+1,转第4步。3步，比较Cs与Cs十的顶点寻本算法除了求回路有已知的好算法外，计算量主要在第找它们的公共点的运算中，这些运算不超出p2*(q-p+w)次，故是好算法14 .证明：H2r *p是(2r+1)连通的。分析：只要证明H2fp不存在少于2r+1个顶点的顶点割集。设V是一个|V|2r+1的任 一顶点子集，可分|V叫2r和|V|=2r两种情形证明。证明：(1)当|V|2r时，根据定理7.3.1的证明，V不是H2r,p的顶点割集，当然更不是在H 2r 0上加些边的H2r 的顶点割集。 A r , pr , 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顶点割集矛盾。若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 = *i0i0n+ 2n 1+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) =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- jij 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=7H 4,8图(ii) H5.8图：r =2,p=8,则在H 4.8中添加连接顶点i+p/2(mod p)的边，其中 1ip/2,：1 一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 i0个奇点，则G中存在k个边互不重的链Q1 Qk ,使得：1 , kE(G) =E(QJ . E)一. E(Qk)分析：一个图的E回路去掉一条边以后，将得到一条 E链。证明：设 V1V2,，Vk,Vk书，V2k为G中的奇数度顶点，k 1在Vi和Vi+k之间用新边ei连 接，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连通图，说明MG1 ,于是工口或K(G)=0 ,如果K(G)=0,则说明g 不连通，如G不连通，显然G不是H图，如K(G)=1则g中存在孤立点，因此有w(G-v)2, 由定理8.2.1G不是H图。若G是二分图 ,则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| |x| =|s|即：切(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) p的顶点u,v,若uv*E(G),则将边uv力口至U G中，得到G+uv,如此反复加边，直到满足d(u)+d(v) p的所有顶点均邻接。由闭包的定义，如 果一个图本身不存在任何一对顶点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连通图Go2 39pp分析：根据定理5.3.1有2q = d(vi),因此q = d(Vi)/2 i 1i =1P而Z d(vi)之P* 6(G),所以qp*S(G)/2,因此如果能判断S(G)3,则有 i 41q之pw 6(G)/2至3P/2之(3p+1)下面的证明关键是判断S(G)3。证明：(1)任取we V(G),由于G是连通的，所以d(w)1op 4,所以GH通路与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)3p,即：2q3p,也即 q 3p/21- 八若p为奇数，于是q -(3p+1)；1(ii)若p为偶数，则3P为偶数，于是q 2(3p+1)；综合以上各种情况，有:1q 至 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,由假设m2 8。再在P的基础上构造一条长度为 m+1的回路C,显然C中包 含的顶点数小2 8,由于p皂28,所以图G至少还有一个顶点v不在该圈中，又由于 G是连通 的，所以v到C上有一条通路P。于是P+C的长度等于通路P的长度的通路构成了一条比 P更 长的通路，这与P是G的一条最长通路矛盾。从而本题可得到证明。证明：(用反证法)设p =VV 栋G的最长通路 淇长度为m,假设m5o由定义知：vm +更ST ,因止匕|sUT|wmM26 ,于是ST#中，事实上，= 2S A SJt = S + T -|st| S - SnT|=2 - SnT 二怕口丁 卜 0,即 STQ。设丫1三$1丁#我从而有G中的长为 m+1的回路C： v1V2“ivivm41Vmvi+v1.因p 26, m+1 W26,所以，C外至少还有一个顶点v0 e V (G)。由G连通可知，有一条 P外的通路与C连接。不妨设 v0vj WE (G) ,1EjEm+1.是有通路P ： V0VjVj 4V1Vi书VmVm由ViVi/V1.且P I A P ,此与P的假设矛盾！ 故结论成立。12、设p(豺阶简单图G的度序列为：d1Wd2Wrqp.证明：若对任何m,117W(p1)/2,均有dmm右p为奇数，还有d1P布与(p1)则G是H图。分析：由定理824,如果p (3)阶简单图G的各顶点度数序列di京2W玄p,而且又t任何mp-m,贝UG是H图。卜面的证明就是利用这个定理来判断当mm。从而G是H图。证明：对任何正整数 m；E,2(1)若p为偶数(p之3),则必有：14mwB1=E_p二1 222即1 m m,再由定理8.2.4知G为H图(2)若p为奇数，则m E p 1 (a)若m m, 22p -1p-1(bm= ，地 pm=p=221 口 r于是 dp_m =d 1 ( p -1)Wd p_m 至(p 1)22 L2 p - p 1 p 12 一 21(p1)+1 = p m,也即 dp_m 至 p m,2从而，由定理8.2.4知，G是H图。13、在图8-8中，如果分别去掉v3, v4和v5,则相应得到的旅行推销员问题的解分别取什么下 界估计值？ 分析：利用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) w(C)上式左边的表达式即是w(C)的下界估计式。解：(1)去掉v3后的最优数T3的权为w(T3)=5+5+1+7=18，而与v3关联的5条边中权最小的两条之权为w(e1)=8,w(e2)=9，因此下界估计值为 w(C3)=18+8+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的权满足。因此只428(C)%(C)E(O|v(G)|), Q中某些顶点可能有重复，且0 (Q)=28(T)在Q中，从v3开始，凡前面出现过的顶点全部删去，得到 G的|v(G)由顶点的一个排列兀。由 于G是完全的，所以兀可以看作G中的一个H回路。在兀中任意边(u,v),在T中对应存在唯一 的(u,v)-通路P,由权的三角不等式有切(u,v)由于将兀中的边(u,v)用T中的P来代替时，就得到Q,因而 (冗)抬(Q)=2o(T澈G中的最优H回路C的权 切(C)tt(n)1是奇数。举出没有完美匹配的k -正则简单图的例子。分析：作G如下：取2k-1个顶点v1,2,v2ki,在奇足标顶点和偶足标顶点间两两连以边外，再连以V1V3,V5v7： ,V2k_5V2k工边，所得图记为G0,显然G0除V2k外其余顶点的度均为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 。22假设M是G的一个完美匹配，则其边应来自k个独立的Go,和跟Vo相关联的一条边。而每个Go,其包含的顶点数为2k-1,所以Go能提供给M的边最多为k-1条，k个这样的Go能提22 k-1供给M的边最多为k*(k-1),因此M最多包含的边为k*(k-1)+1=k 2-(k-1)0时，Vi与v邻接，并规定最后可下子的一方获胜。若规定执黑子者先下子，试证明执 黑子的一方有取胜的策略当且仅当 G无完美匹配。分析：假设G有完美匹配，则G的每个顶点都是M-饱和点，这样先下者无论取哪个顶点，后下 者都可取其相邻的M-饱和点，这样先下的人必输；因此先下的人如要赢的话，G中肯定无完美匹 配。反过来，如果G中无完美匹配，由于任何图都有最大匹配，则可找到 G的一个最大匹配 M,由 于M不是完美匹配，因此 G中存在M-非饱和点v,先下的黑方就可找到这个点下，则与 v相邻 的下一个点必是M-饱和点，不然，M Uuv就是一个更大的匹配，与M是最大匹配矛盾。同理G 中不存在M可增广路，故黑方所选vi必是M饱和点，如此下去，最后必是白方无子可下，故黑 方必胜。证明：必要性(反证法) 若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不是二分图，则上述条件未必充分。分析：由定理9.1.2Hall定理，对于具有二划分(X,Y)的二分图，G有饱和X中每个顶点的匹配 当且仅当对任意的SX ,|S|n是一个(0,1)矩阵.将M m沏表示成一个二分图G(V1,V2 ,E),V1 =u1,，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与V邻接当且仅当U与V所在的方格有公共边。则该问题等价于判断相应图G是否有完美匹配，解：按照分析，构造图G如下：则有O(G1=u|,由定理9.1.3可判断它没有完美匹 配。因此不能用5个1父2的长方表将图9-13中的10个1父1正方形完全遮盖住。110 .试证明：G是二分图当且仅当对 G的每个子图H均有 a(H ) - |V(H) |o2分析：若6= (X,Y)是二分图，显然X和Y都构成G的点独立集，所以G的最大独立数ct(G)|X| , 且u(G)平|;而二分图的每个子图显然也是二分图。证明：必要性.设G是二分图，于是 G的任何子图 H也是二分图，设 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 是二分图。4811 .试证明：G是二分图当且仅当对 G的每个适合6(H ) 0的子图H ,均有a(H) = P(H). 分析：ot(G)是指G的最大独立集，P 0 ,即H无孤立点。显然H也是二分图， 设H =(X,Y),且| X以丫 |。于是， u(H ) =|X |。而一条边最多覆盖一个顶点，故 pH) |X |o 但由于 H 无孤立点，因此，P(H) s(H)。矛盾。故 G 必为二分图。12 .设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 o1 ,n由对任何uWX,vWY, d(u)之d(v),得 d(u)至d d(v),但由于S中的点关联的边u Sv三Ng (S)都是Ng (S)的点关联的边，因此d d(u)d(ut)。矛盾。故G中存在饱和X的匹配。13.证明(Hall定理的推广)：在以G(X,Y)为二划分的二分图G中，最大匹配数二(G)为(G) =min| X -S| |Ng(s)|s x-分析：由定理9.2.2有：如果一个图G是二分图，则u(G) = P(G) , a(a)是G的最大匹配数，P(G)是G的最小覆盖。因此如果能说明 mjn|X-S|Ng(S)|等于目(G)的话，则本题得以证明。s x证明：由于X SNg(S)H,所以 |XS|+|Ng(S)| = XSjNg(S)|显然 X S3Ng (S)是G的一个覆盖，而G的任意一个覆盖都可以写成 X S= N g (S)的形式，所以 FG) = min|X-S| |Ng(S)|因此有：(G) = -(G)=xmin|X-S| |Ng(S)|S x4914 .证明：在无孤立点的二分图 G中，最大独立集的顶点集“(G)等于最小边覆盖数P (H)。证明：参见题1115 .在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)
展开阅读全文