电子科技大学图论及其应用5班第4-5章作业.docx

《电子科技大学图论及其应用5班第4-5章作业.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题43：1）、画一个有Euler闭迹和Hamilton圈的图。2）、画一个有Euler闭迹但没有Hamilton圈的图。3）、画一个有Hamilton圈但没有Euler闭迹的图4）、画一个既没有Hamilton圈也没有Euler闭迹的图7、证明：将G中的孤立点去掉后的图为G1，则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1，在G1–S1中去除孤立的点，得到一个新的图G2，显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2，这样一直下去，指导Gm中有圈Sm，且Gm-Sm都是孤立的点。这

2、样E(G)=E(G1)并E(G2)…..并E(Gm).命题得证。10、证明：1）、如果G不是而连通的图，那么G存在割点v或则G是不连通的，G-v的连通分支数大于等于2.由定理：若G是H图，则对于V的每个飞空真子集S，均有G-S的连通分支数小于等于S的顶点数，知，G是非H图。2）、G是2部图，且

3、X

4、<

5、Y

6、,则有G-X的连通分支数等于

7、Y

8、>

9、X

10、由上边的定理知，G是非H图。12、证明：假设G中新加入的一点，为V,它和G中的每一个顶点均相连，这样得到新的图G^,这样G^的度序列为(d1+1,d2+1……,dv+1,V)。因为不存在正整

11、数m<(v+1)/2,使其满足dm=2)。假设K方体的顶点坐标为：(x1,x2…,xk)，取(x1,x2,….,xk-1,0)和(x1,x2,…,xk-1,1)两个顶点之间的边的全体集合为M，这样M,中的边均不相邻，所以M是一个匹配，且

12、M

13、=2^(k-1)。K方体一共有2^k个顶点，所以K方

14、体的每一个顶点均是M饱和的，所以M是K方体的一个完美匹配。2）、球K2n，Kn,n中不相同的完美匹配个数。K2n中的任一个顶点有2n-1中方法被匹配，选择其中的一条边后，则剩下2(n-1)个顶点，其导出子图为K2(n-1。所以由归纳法K2n的完美匹配有(2n-1)n个。对Kn,n做相似的归纳，得到Kn,n的完美匹配共有n个。所以他们有不同的完美匹配个数。1、证明：一棵树最多只有一个完美匹配。反证法：假设数有两个不同的完美匹配M1和M2，M1和M2的交为空，并且T[M1^M2]中每个顶点的度数都为2，这样可以知道T中包含圈，这与已知T是

15、树矛盾，所以一棵树最多只有一个完美匹配。6、证明：K2n的1-因子分解的数目为(2n)!/(2^n*n!)。因为K2n的不同完美匹配的个数为(2n-1)!!。所以，K2n的一因子分解数目为(2n-1)!!个，即2n)!/(2^n*n!)，命题得证。7、K9可表示为四个生成圈之和。答：K4n+1=K2(2n)+1,所以可分解为2n个边不重的2因子之和.K9=K2*4+1，所以K9可以分解为四个边不重的2因子之和，具体路径如下：C1=p9p1p8p2p7p3p6p4p5p9C2=p9p2p1p3p8p4p7p5p6p9C3=p9p3p2p

16、4p1p5p8p6p7p9C4=p9p4p3p5p2p6p1p7p8p9生成圈Hi是V2n+1与Pi的两个端点连接生成的，所以可以将K9表示成四个生成圈之和。13求解：所以最小的权值和为30。