电子科大-杨春-图论第二次作业

第四章3.7.证明：因为G中无奇点，去除度为零的点，则G’中必可以找到一条Eular闭迹，也就是初始圈C1，之后去掉C1所包含的边，去点度为零的点，则在新图G’’中每个点的度数仍为偶数，在G’中可以找到一条Eular闭迹，也就是圈C2，以此类推，可以寻到C3、.....、Cm，最后可以得到CECECEGEm21。10.证明：(1)如果G不是二连通的，则G存在割点或者不是连通的。若G不是连通的，则G不是Hamilton图；若G中存在割点v，则G-v的连通分支数大于等于2，由定理：若G是H图，则对于V的每个非空子集S，均有SSG可知，G为非H图。(2)不妨设|X||Y|,则G-X的连通分支数|Y||X|，由（1）中的定理可知，G为非H图。12.证明：假设G中新加入的一点，为V，它和G中的每一个顶点均相连，这样得到新的图G,这样G的度序列为ndddn,,......,,11121。因为不存在正整数m(n+1)/2,使其满足dmm和dn-m+1n-m,即不存在mn/2,满足dm=mm+1和dn-m+1n-m+1=(n+1)-m。由定理知，G中含有Hamilton圈C，这样G^-C就是G的H路，命题得证。第五章1.（1）证明：假设K方体的顶点坐标为：(x1,x2…,xk)，取(x1,x2,….,xk-1,0)和(x1,x2,…,xk-1,1)两个顶点之间的边的全体集合为M，这样M,中的边均不相邻，所以M是一个匹配，且|M|=2^(k-1)。K方体一共有2^k个顶点，所以K方体的每一个顶点均是M饱和的，所以M是K方体的一个完美匹配。（2）K2n中的任一个顶点有2n-1中方法被匹配，选择其中的一条边后，则剩下2(n-1)个顶点，其导出子图为K2(n-1。所以由归纳法K2n的完美匹配有(2n-1)n个。对Kn,n做相似的归纳，得到Kn,n的完美匹配共有n个。2.证明：反证法：假设数有两个不同的完美匹配M1和M2，M1和M2的交为空，并且T[M1^M2]中每个顶点的度数都为2，这样可以知道T中包含圈，这与已知T是树矛盾，所以一棵树最多只有一个完美匹配。6.证明：因为K2n的不同完美匹配的个数为(2n-1)!!。所以，K2n的一因子分解数目为(2n-1)!!个，即2n)!/(2^n*n!)，命题得证。7.解：.KK1429，所以K9可以分解为四个边不重的2因子之和。13.解：最小的权值和为30。