第四章。
3(1).有欧拉闭迹和h圈。
2).有欧拉闭迹但没有h圈。
3).有h圈无欧拉闭迹。
4).无欧拉闭迹且没有h圈。
4：证：若g不是h图，由chvatal定理知，g度弱于某个图，故：
这与题目已知条件相矛盾，故g是h图。
8：证：不失一般性，设g是连通图，是g的2k个奇点，连接，得到，则得到图，则是欧拉图，设c是中的欧拉闭迹，删除c中的，即可得到k条边不重复的迹，使得。
10(1)若g不是二连通图，那么g不连通或者有割点u，则w，故g是非h图。
2). 若g是具有二分类的偶图，且，若假设则，故g是非h图。
11：设r是g中的h路，则对于每个真子集s，有w，又：
ww，故w.
12：设u是g外一点，将u和g中的每个点连接得到图，则g的度序列为，故有题意知，不存在小于的正整数m，使得，故由chvatal定理知，图是h图，则g有h路。
15：(1)由图的闭包定义可知，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点加边得到。故图的闭包算法如下：
第一步：令；
第二步：在中求顶点，使得：
第三步：如果，则转到第四步；否则，停止，则可得到g的闭包。
第四步：令，转到第二步。
复杂性分析：由其算法我们可得出其总运算量为：
故该算法能够在多项式时间内被解决，故该算法是一个好算法。
2).设计算法如下：
第一步：在闭包构造中，将加入的边依次加入次序记为，在中任意取出一个h圈，令k=n;
第二步：若不在中，令；否则转到第三步。
第三步：设，令；求中两个相邻点u和v使得，u，v依序排列在上，且有：，令：
第四步：若k=1，转到第五步；否则，令k=k-1,转第二步；
第五步：停止。为g的h圈。
算法的复杂性分析：因为该算法进行了n次循环，每次循环中找到满足要求的邻接顶点u和v至多需要n-3次判断，所以总的运算量：n(n-3)。是一个好算法。
第五章。1：(1)证：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。
若划分k方体的2k个顶点，把坐标之和为偶数的顶点归入x，否则归入y。显然，x中顶点互不邻接，y中顶点也如此。所以k方体是偶图。
又k方体的每个顶点度数为k,所以k方体是k正则偶图。所以由推论可知：k方体存在完美匹配。
2).解k2n的任意一个顶点有2n-1中不同的方法被匹配。所以k2n的不同完美匹配个数等于(2n-1)k2n-2,如此推下去，可以归纳出k2n的不同完美匹配个数为：
(2n-1)!!同理，k n, n的不同完美匹配个数为：(n)!。
2：若不然，设m1与m2是树t的两个不同的完美匹配，那么m1δm2≠φ,且t[m1δm2]每个顶点度数为2，即它存在圈，于是推出t中有圈，矛盾。故一棵树中最多只有一个完美匹配。
7：解：设。
作如下四条路：
故其四个生成圈如下：
8：证明：k6n-2= k 2(3n-1) ,所以，可以分解为6n-3个边不重的1因子之和。
而任意3个1因子可以并成一个3因子。所以，共可以并成2n-1个3因子。即k6n-2可以分解为2n-1个3因子的和。
10：证明：因δ(g)≥n/2+1 ,由狄拉克定理：
n阶图g有h圈c .又因n为偶数，所以c为偶圈。于是由c可得到g的两个1因子。
设其中一个为f1。设g1=g-f1。则δ(g1)≥n/2。
于是g1中有h圈c1.作h=c1∪f1。显然h是g的一个3因子。
19:证明：k4n+1= k 2(2n)+1 , 所以，可以分解为2n个边不重的2因子之和。
而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即k4n+1可以分解为n个4因子的和。
图论第二次作业
1 某乡 计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表所示。乡镇府如何选择修建公路的路线使总成本最低。2在下图中，求a到h i的最短路及最短路长，并对图 a 和 b 的结果进行比较。图。3已知某设备可继续使用5年，也可以在每年年末...
图论第二次作业
习题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 ...
图论第二次上交作业
班级 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 证 因为四个...