习题43．解：
7.证明：将g中孤立点除去后的图记g1，则g1也无奇数度点，且δ（g1）>=2,从而可知g1有一个圈c1，在图g1-c1中去孤立点，得图g2；显然g2仍无奇数点，且δ（g2）>=2,所以g2中有一圈c2，如此下去，直至gm中有圈cm,且gm-cm全为孤立点为止。
于是e(g)=e(c1)∪e(c2)∪.e(cm).
10.证明：
1）若g不是2连通的，则g不连通或存在割点v,有ω（g-x）>=2，由定理知g是非hamilton图。
2）设g是2部图，其划分为（x,y）,且|x|<|y|,则有ω（g-x）=|y|>|x|,由定理知g是非hamilton图。
12.证明：
对g加入一个新顶点v，它和g中的每一个顶点均相连，所得之图记为g1，于是g1的度序列为（d1+1,d2+1,..dv+1,v）,由已知条件可知，不存在m<(v+1)/2,它满足dm<=m和dv-m+1习题5
1.（1）证明：
设k方体顶点坐标为(x1 ,x2,…,xk),我们取(x1 ,x2,…,xk-1,0),和(x1 ,x2,…,xk-1,1) 之间的全体边所成之集为m.
显然，m中的边均不相邻接，所以m是一个匹配，又容易知道：|m|=2k-1.因为k方体的顶点数是2k,所以k方体中的每一个顶点都是m-饱和的，所以m是完美匹配。
2）解：k2n的任意一个顶点有2n-1种不同的方法被匹配，一旦选定某一边属于m之后，剩下(2n-1)个顶点，它们的导出子图是k2（n-1）如此推下去，可以归纳出k2n的不同完美匹配个数为：(2n-1)!!
同样的推导方法可归纳出kn, n的不同完美匹配个数为：n!
2.证明：假设原命题不成立，设m1与m2是树t的两个不同的完美匹配，那么m1δm2≠φ,容易知道：
t[m1δm2]每个非空部分顶点度数为2，即它包含圈，这和t是树矛盾。所以原命题得证。
6.证明：k2n的不同完美匹配的个数为(2n-1)！！所以，k2n的1-因子分解数目为(2n-1)！！个。即：
(2n-1)!!2n)!/
7.解：把k9中的9个顶点编号，记以0,1,2,3,4,5,6,7,8将0放在圆的中心，而其余的8个顶点均匀地放在圆周上；令g1=0 1 2(8)3(7)4(6)(5)0,g1是k2n+1的一个2-因子，将c1以0为心按逆时针每旋转一个顶点，就产生一个新的2-因子，于是旋转4次后共产生4个2-因子，记为c1,c2,c3,c4,显然ci之间两边互不相交，且g=g1∪g2∪g3∪g4
13.解：将方阵的每行视为x中一点，每列视为y中一点，方阵的元素即为完全2部图（x,y）的各边的权，方阵的对角线就是2-部图的完美匹配。
本题就是求最小权的完美匹配。用kuhn-munkres算法得到最优的值为：
19.证明：
所以，可以分解为2n个边补充的2因子之和。而任意2个2因子可以合并成一个4因子。所以，共可以并成n个4因子。即可以分解为n个4因子的和。
图论第二次作业
1 某乡 计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表所示。乡镇府如何选择修建公路的路线使总成本最低。2在下图中，求a到h i的最短路及最短路长，并对图 a 和 b 的结果进行比较。图。3已知某设备可继续使用5年，也可以在每年年末...
图论第二次作业
第四章。3 1 有欧拉闭迹和h圈。2 有欧拉闭迹但没有h圈。3 有h圈无欧拉闭迹。4 无欧拉闭迹且没有h圈。4 证 若g不是h图，由chvatal定理知，g度弱于某个图，故 这与题目已知条件相矛盾，故g是h图。8 证 不失一般性，设g是连通图，是g的2k个奇点，连接，得到，则得到图，则是欧拉图，设c...
图论第二次上交作业
班级 1班姓名 关科科学号 201421260251 1.4 证 将图1 28的两图顶点标号为如下的 a 与 b 图。作映射f f vi ui 1 i 10 可证明，对vivje a 有f vivj uiuje b 1 i 10,1j 10 由图的同构定义知，图中两个图是同构的。1.5 证 因为四个...