电子科大图论-第二次作业(4、5章)-答案.doc

《电子科大图论-第二次作业(4、5章)-答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题四3.（1）画一个有Euler闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下：(1)一个有Euler闭迹和Hamilton圈的图；(2)一个有Euler闭迹但没有Hamilton圈的图；(3)一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.7.将G中的孤立点去

2、掉后的图为G1，则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1，在G1 –S1中去除孤立的点，得到一个新的图G2，显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2，这样一直下去，指导Gm中有圈Sm，且Gm-Sm都是孤立的点。这样E(G) = E(G1)并E(G2)…并E(Gm).命题得证。10．证明：若：（1）不是二连通图，或者（2）是具有二分类的偶图，这里,则是非Hamilton图。证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本上的

3、相关定理：若是Hamilton图，则对于的任意非空顶点集，有：,则该定理的逆否命题也成立，所以可以得出：若不是二连通图，则是非Hamilton图(2)因为是具有二分类的偶图，又因为，在这里假设,则有,也就是说：对于的非空顶点集，有：成立，则可以得出则是非Hamilton图。习题五1.(1)证明：每个k方体都有完美匹配(k大于等于2)(2)求K2n和Kn,n中不同的完美匹配的个数。证明一：证明每个k方体都是k正则偶图。事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，

4、两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。由推论：k方体存在完美匹配。证明二：直接在k方体中找出完美匹配。设k方体顶点二进制码为(x1,x2,…,xk),我们取(x1,x2,…,xk-1,0),和(x1,x2,…,xk-1,1)之间的全体边所成之集为M.显然，M中的边均不相邻接，所以作成k方体

5、的匹配，又容易知道：

6、M

7、=2k-1.所以M是完美匹配。(2)我们用归纳法求K2n和Kn,n中不同的完美匹配的个数。K2n的任意一个顶点有2n-1种不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出K2n的不同完美匹配个数为：(2n-1)!!同样的推导方法可归纳出Kn,n的不同完美匹配个数为：n!6．证明：K2n的1-因子分解的数目为(2n)!/(2^n*n!)。     因为 K2n的不同完美匹配的个数为(2n-1)!!。所以，K2n的一因子分解数目为

8、(2n-1)!!个，即2n)!/(2^n*n!)，命题得证。7．将表示为四个生成圈之和。证明：K4n+1=K2(2n)+1,所以，可以分解为2n个边不重的2因子之和。而。所以可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：,则的四条路径为：,,,,则生成圈是与的两个端点连线生成的。所以可以将表示为四个生成圈之和。13.所以最小的权值之和为30