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

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第四章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。

1 / 3
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功