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

电子科技大学图论及其应用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(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|<|Y|,则有G-X的连通分支数等于|Y|>|X|由上边的定理知，G是非H图。 12、证明： 假设G中新加入的一点，为V,它和G中的每一个顶点均相连，这样得到新的图G,这样G的度序列为(d1+1,d2+1,dv+1,V)。因为不存在正整数m<(v+1)/2,使其满足dm<m和dv-m+1<v-m,即不存在m<(v+1)/2,满足dm+1<=m和dv-m+1<v-m+1 = (v+1) m。由定理知，G中含有Hamilton圈C，这样G-C就是G的H路，命题得证。 习题5 1、 1）、证明：每个k方体都有完美匹配(k>=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个。所以他们有不同的完美匹配个数。 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。