图论第二次作业
一、第四章
4.3（1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：
（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：
（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：
（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：
4.7证明：若G 没有奇点，则存在边不重的圈C 1,C 1,....,C m ,使得E(G)=E(C 1) E(C 2) ..... E(C m )。

证明：将G 中孤立点除去后的图记为G 1,则G 1也没有奇点，且δ(G 1)≥2，则G 1含圈C 1，在去掉G 1-E(C 1)的孤立点后，得图G 2，显然G 2仍无奇度点，且(G 2)≥2，从而G 2含圈C 2，
如此重复下去，直到圈C m ，且G m -E(C m )全为孤立点为止，于是得到E(G) E(C 1) E(C 2) ... E(C m )。

4.10证明：若
（1）G 不是二连通图，或者
（2）G 是具有二分类(X,Y)的偶图，这里|X|≠|Y|， 则G 是非Hamilton 图。

证明：（1）因为G 不是二连通图，则G 不连通或者存在割点V ，有w(GV)2，由相关定理得：若G 是Hamilton 图，则对于V(G)的任意非空顶点集S ，有：w(GS)S ，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。

（2）因为G 是具有二分类(X,Y)的偶图，又因为|X|≠|Y|，在这里假设|X|≠|Y|，则有w(G-X)=Y>X ，也就是说：对于V(G)的非空顶点集S ，有：w(G-S)>S 成立，则可以得出G 是非Hamilton 图。

4.12设G 是有度序列(d1,d2,...,dn)的非平凡简单图，这里d 1≤d 2≤...≤d n ，证明：若不存在小于(n+1)/2的正整数m ，使得d m <m 且d n-m+1<n-m ，则G 有Hamliton 路。

证明：在G 之外加上一个新点V ，把它和G 的其余各点连接，得图G1：
G1的度序列为：(d 1+1,d 2+1...d n+1,n)，由已知：不存在小于(n1)/2的正整数m ，使得d m +1
≤m 且d n-m+1<n-m+1=(n+1)-m 。

于是由度序列判定定理知：G1是Hamilton 路，则G 有Hamliton 路。

二、第五章作业
5.1（1）证明：每个k 方体都有完美匹配（k ≥2）; （2）求K 2n 和K n,n 中不同的完美匹配的个数。

证明：（1）证明每个k 方体都是k 正则偶图即可。

事实上，由k 方体的构造：k 方体有2k
个顶点，每个顶点可以用长度为k 的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。

如果我们划分k 方体的2k 个顶点，把坐标之和为偶数的顶点归入X ，其余归入Y 。

显然，X 中顶点互不邻接，Y 中顶点也如此。

所以k 方体是偶图。

又不难知道k 方体的每个顶点度数为k ，所以k 方体是k 正则偶图。

由推论得：k 方体存在完美匹配。

解：（2）利用归纳法求K 2n 和K n,n 中不同的完美匹配的个数。

K 2n 的任意一个顶点有2n-1中不同的方法被匹配。

所以K 2n 的不同完美匹配个数等于(2n-1)K 2n-2，如此递推下去，可以归纳出K 2n 的不同完美匹配个数为：(2n-1)!!；利用同样的方法可归纳出Kn,n 的不同完美匹配个数为：n!。

5.2证明：一棵树最多只有一个完美匹配。

证明：若不然，设M1和M2是树T 的两个不同的完美匹配，那么M1∆M ≠2，容易知道：T[M1∆M2]每个非空部分顶点度数为2，即它存在圈，于是推出T 中有圈，矛盾。

所以一棵树最多只有一个完美匹配。

5.6证明：K2n 的1-因子分解的数目为(2n)!/2n n!。

证明：由结论知：K 2n 不同完美匹配的个数为(2n-1)!!。

所以，K2n 的1-因子分解 数目为(2n-1)!!个。

即：(2n-1)!!=(2n)!/2n n! 5.7将K 9表示为四个生成圈之和。

解：K 4n+1=K 2(2n)+1，所以，可以分解成2n 个边不重的2因子之和。

而K 9=K 2*4+1。

所以K 9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为： P i =V i V i-1+V i +1V i -2+V i +2V i-3...V in V in 则K 9的四条路径为： P 1=V 1V 8V 2V 7V 3V 6V 4V 5 P 2=V 2V 1V 3V 8V 4V 7V 5V 6 P 3=V 3V 2V 4V 1V 5V 8V 6V 7 P 4=V 4V 3V 5V 2V 6V 1V 7V 8
则生成圈Hi 是V 2n+1与Pi 的两个端点连线生成的。

所以可将K9表示为四个生成圈之和。

5.13所谓n ×n 矩阵的一条对角线是指两两不同行不同列的n 个矩阵元素组成的集。

对角线的权是指它的n 个元素的和。

找出下列矩阵具有最小权的对角线：
⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎣⎡8 9 7 5 47 10 13 6 66 9 12 5 84 7 5 6 711 10
8 5 4
解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4，
将其所在的行和列删除，得到的矩阵为
⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎣⎡4 7 5 66 9 12 57 10 13 68 9 7 5 再从此矩阵的第一行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)的4。

依次类推，继续得到坐标是(3,2)的5，(5,3)的7，(4,4)的10。

所以最小权为：4+4+5+7+10=30。

5.19证明:对n ≥1,K 4n+1有一个4-因子分解。

证明:K4n+1=K2(2n)+1所以，可以分解为2n 个边不重的2因子之和。

而任意2个2因子可以并成一个4因子。

所以，共可以并成n 个4因子。

即K 4n+1可以分解为n 个4因子的和。