《电子科技大学图论及其应用5班第45章作业.docx》由会员分享,可在线阅读,更多相关《电子科技大学图论及其应用5班第45章作业.docx(3页珍藏版)》请在三一办公上搜索。
1、电子科技大学图论及其应用5班第45章作业习题4 3: 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都是孤立的点。这样E(
2、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部图,且|X|X|由上边的定理知,G是非H图。 12、证明: 假设G中新加入的一点,为V,它和G中的每一个顶点均相连,这样得到新的图G,这样G的度序列为(d1+1,d2+1,dv+1,V)。因为不存在正整数m(v+1)/2,使其满足dmm和dv-m+1v-m,即不存在m(v+1)/2,满足dm+1=m和dv-m
3、+1=2)。 假设K方体的顶点坐标为:(x1,x2,xk),取(x1,x2,.,xk-1,0)和(x1,x2,xk-1,1)两个顶点之间的边的全体集合为M,这样M,中的边均不相邻,所以M是一个匹配,且|M| = 2(k-1)。K方体一共有2k个顶点,所以K方体的每一个顶点均是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个。所以他们有不
4、同的完美匹配个数。 2、 证明:一棵树最多只有一个完美匹配。 反证法:假设数有两个不同的完美匹配M1和M2,M1和M2的交为空,并且TM1M2中每个顶点的度数都为2,这样可以知道T中包含圈,这与已知T是树矛盾,所以一棵树最多只有一个完美匹配。 6、证明:K2n的1-因子分解的数目为(2n)!/(2n*n!)。 因为 K2n的不同完美匹配的个数为(2n-1)!。所以,K2n的一因子分解数目为(2n-1)!个,即2n)!/(2n*n!),命题得证。 7、K9可表示为四个生成圈之和。 答:K4n+1 = K2(2n)+1,所以可分解为2n个边不重的2因子之和.K9 = K2*4+1,所以K9可以分解为四个边不重的2因子之和,具体路径如下: C1=p9 p1 p8 p2 p7 p3 p6 p4 p5 p9 C2=p9 p2 p1 p3 p8 p4 p7 p5 p6 p9 C3=p9 p3 p2 p4 p1 p5 p8 p6 p7 p9 C4=p9 p4 p3 p5 p2 p6 p1 p7 p8 p9 生成圈Hi是V2n+1与Pi的两个端点连接生成的,所以可以将K9表示成四个生成圈之和。 13求解: 所以最小的权值和为30。