《电子科大图论-第二次作业(4、5章)-答案.docx》由会员分享，可在线阅读，更多相关《电子科大图论-第二次作业(4、5章)-答案.docx（5页珍藏版）》请在三一文库上搜索。
1、习题四3. (1)Euler闭迹和Hamilton圈的图；Euler闭迹但没有Hamilton圈的图； Hamilton圈但没有Euler闭迹的图； 画一个即没有Hamilton圈也没有Euler闭迹的图;画一个有画一个有画一个有(2)(3)(4) 解：找到的图如下：(1)一个有Euler闭迹和Hamilton圈的图;(2) 一个有Euler闭迹但没有一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.7.将G中的孤立点去掉后的图为 G1，则G1也是没有奇度点的，且G1的最小 度大于等于2.则G1存在一个圈S1,在G1 - S1中去除孤
2、立的点，得到一个新的 图G2,显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在 一个圈S2，这样一直下去，指导 Gm中有圈Sm，且Gm-Sm都是孤立的点。这 样E(G) = E(G1)并E(G2)并E(Gm).命题得证。10 .证明：若:(1) G不是二连通图，或者(2) G是具有二分类(托Y)的偶图，这里|X|# IY|,则是非Hamilton图。证明：(1) M不是二连通图，则;G不连通或者存在割点|v,阿(G-可2|,由于课本上的相关定理：若时是Hamilton图，则对于v (G)的任意非空顶点集S ,有:lw(G - S) ,则该定理的逆否命题也成立，所以可以得出：若
3、不是二连通图,则血是非Hamilton图 因为G是具有二分类(丸Y)的偶图，又因为凶尹|Y|，在这里假设|X| |X|,也就是说：对于M G)的非空顶点集S，有:I成立，则可以得出则是非Hamilton图。习题五1. (1)证明：每个k方体都有完美匹配(k大于等于2)(2)求K2n和Kn,n中不同的完美匹配的个数。证明一：证明每个k方体都是k正则偶图。事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进 制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入 X，否则 归入丫。显然，X中顶点互不邻接
4、，丫中顶点也如此。所以k方体是偶图。又不 难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。由推论：k方体存在完美匹配。证明二：直接在k方体中找出完美匹配。设k方体顶点二进制码为(X1 ,X2,X),我们取(X1 ,X2,x-1,0),和 (X1 ,X2,x-1,1)之间的全体边所成之集为 M.显然，M中的边均不相邻接，所以 作成k方体的匹配，又容易知道：IMFQk1 所以M是完美匹配。 我们用归纳法求K2n和Kn,n中不同的完美匹配的个数。K2n的任意一个顶点有2n-1种不同的方法被匹配。所以 K2n的不同完美匹配个 数等于(2n-1)K2n-2,如此推下去，可以归纳出 K2n的不同完
5、美匹配个数为：(2n-1)! 同样的推导方法可归纳出K n, n的不同完美匹配个数为：n!6 .证明：K2n的1-因子分解的数目为(2n)!/(2八n*n!)。因为K2n的不同完美匹配的个数为(2n-1)!。所以，K2n的一因子分解数目为 (2n-1)!个，即 2n)!/(2八n*n!)，命题得证。7 .将Kq表示为四个生成圈之和。证明：K4n+1= K 2(2n)+1 ,所以，可以分解为2n个边不重的2因子之和。而Kf严 K? T 十 1。所以心可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为:则卜啲四条路径为:卩1 = 代抚7必畀池, 卩2 =匕5罪*4外評&)P厂吋2T1X屮M,则生成圈 圈之和。|H|是勺n+1与Pi的两个端点连线生成的。所以可以将Kq表示为四个生成13.所以最小的权值之和为30；v. -rJ-.-, - K 打：.V .- F:沖壮徳吾騷疗；疔先1 心曲曲辭噹賈护”八:Y