《湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学.docx》由会员分享，可在线阅读，更多相关《湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学.docx（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) =1。因T是树，所以存在(u
2、,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 。于是，存在
3、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,
4、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
5、 00最长通路长度为4；（2） q0Qq最长通路长度为 3;O(3)最长通路长度为2。对于（1），把每个顶点看作是一个空，不同的顶点序列对应不同的树，但由于对称性12345和54321所形成的树应该是同一棵树，因此这种情况下所有有标记的树的数目为：5! /2=60个；对于（2）,把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为4C5 *4!,但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构成的数是一样的。因此这种情况下所有有标记的树的数目为：C54 *4! /2=6
6、0个；对于（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阶的树。又
7、由定理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
8、)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算法的初值及
9、终止条件，可知 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
10、,入(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
11、,则从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|
12、=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的任意
13、两个顶点由至少两条边不重的通路所 连通.分析：这个题的证明关键是理解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
14、中，因而从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的这个块肯定存在割点，则可导出矛盾。本 题使用反证
15、法。证明：设K是G的一个块，若k既不是K2也不是奇回路，则k至少有三个顶点，且存在 割边e=uv于是u,v中必有一个是割点，此与k是块相矛盾。11 .证明：不是块的连通图G至少有两个块，其中每个块恰含一个割点.分析：一个图不是块，按照块的定义，这个图肯定含有割点 v,对图分块的时候也应该以割 点为标准进行，而且分得的块中必定含这个割点，否则所得到的子图一定不是极大不可分子 图，从而不会是一个块。证明：由块的定义知，若图G不是块且连通，则G有割点，依次在有割点的地方将 G分解 成块，一个割点可分成两块，每个块中含 G中的一个割点。如下图Go易知u,v是割点，G可分成四个块K1K4。其中每个块恰含
16、一个割点。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又
17、是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个公共点，则
18、它们属于同一块。止匕外，由割边的定义知，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步
19、。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的不同分支。考 察顶点
20、集合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
21、 和含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 (
22、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,：
23、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
24、*被分解成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|
25、,如果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
26、的一条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
27、)对于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的连线
28、就构成了一个回路，这样与 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的通路。先找
29、到图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
30、,即 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的各顶
31、点度数序列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中，如果分别
32、去掉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
33、，因此下界估计值为 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
34、的权满足。因此只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,在奇足标顶点和偶足标顶点间两两连以边外，