当前位置:文档之家› 图论第二次作业

图论第二次作业

图论第二次作业
一、第四章
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 ,使得
)()()()(21m C E C E C E G E •••=。

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

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

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

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

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

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

于是由度序列判定定理知:G 1是Hamilton 路,则G 有Hamliton 路。

二、 第五章作业
5.1 (1)证明:每个k 方体都有完美匹配(2≥k );
(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)!!;利用同样的方法可归纳出K n,n 的不同完美匹配个数为:n!。

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

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

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

5.6 证明:K 2n 的1-因子分解的数目为
!2)!2(n n n •。

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

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

即:
!
2)!2(!)!12(n n n n •=-
5.7 将K 9表示为四个生成圈之和。

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

而K 9=K 2*4+1。

所以K 9可以表示为四个边不重的2因子之和,对于每个分解出的因子的路径为:
n i n i i i i i i i i v v v v v v v v P +--+-+-⋅⋅⋅=32211
则K 9的四条路径为:
,,
,
,
871625344768514233657483122546372811v v v v v v v v P v v v v v v v v P v v v v v v v v P v v v v v v v v P ====
则生成圈H i 是V 2n+1与P i 的两个端点连线生成的。

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

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

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

找出下列矩阵具有最小权的对角线:
⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎣⎡897547101366
691258475671110854 解:首先从第一行第一列开始,找出矩阵中的最小元素,发现为坐标是(1,1)的4,将其所在的行和列删除,得到的矩阵为
⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎣⎡8975710136691254756 再从此矩阵的第一行第一列开始,找出矩阵中的最小元素,发现为原坐标是(2,5)的4。

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

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

相关主题