护理专业自我评价-法国商务签证

图论第二次作业


一、 第四章
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< br>1
)
的孤立点后，得图
G
2
，显然
G
2仍无奇度点，且

(G
2
)2
，从而
G
2< br>含圈
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(Gv)2
，
由相关定理得：若G是Hamilton图，则对于v(G )的任意非空顶点集S，有：
w(GS)S
，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则
G是非Hamilton图。
（2）因为G是具有二分类
(X,Y )
的偶图，又因为
XY
，在这里假设
XY
，
则有
w(GX)YX
，也就是说：对于v(G)的非空顶点集S，有：
w(GS)S< br>成立，则可以得出G是非Hamilton图。

4.12 设G是有度序列
(d
1
,d
2
,,d
n
)
的非平凡简单图， 这里
d
1
d
2
d
n
，证明：若不存在 小于
d
nm1
nm
，则G有Hamliton路。
证明：在G之外加上一个新点v，把它和G的其余各点连接，得图G
1
：
( n1)
的正整数m，使得
d
m
m
且
2

G
1
的度序列为：
(d
1
1,d
2
1, ,d
n
1,n)
，由已知：不存在小于
(n1)
的正整数2

m，使得
d
m
1m
且
d
nm1
1nm1(n1)m
。于是由度序列判定定理知：
G
1
是Hamilton路，则G有Hamliton路。



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

证明：（1）证明每个k方体都是k正则偶图即可。
事实上，由k方体的构造：k方体有2< br>k
个顶点，每个顶点可以用长度为k的二进
制码来表示，两个顶点连线当且仅当代表两个 顶点的二进制码只有一位坐标不
同。如果我们划分k方体的2
k
个顶点，把坐标之和为 偶数的顶点归入X，其余
归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又不
难知道k方体的每个顶点度数为k，所以k方体是k正则偶图。
由推论得：k方体存在完美匹配。
解：（2）利用归纳法求K
2n
和Kn,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的两个不同的完美匹配，那么
M
1
M
2


，
容易知道：
T[M
1
M
2
]
每个非空部分顶点度数为2，即它存在圈，于是推出T中
有圈，矛盾。所以一棵树最多只有 一个完美匹配。

5.6 证明：K
2n
的1-因子分解的数目为
数目为(2n-1)!!个。即：
(2n1)!!
(2n)!
。
2
n
n!
证 明：由结论知：K
2n
不同完美匹配的个数为(2n-1)!!。所以，K
2n
的1-因子分解
(2n)!

n
2n!

5.7 将K
9
表示为四个生成圈之和。

解：K
4n+1
=K2(2n)+1
，所以，可以分解成2n个边不重的2因子之和。而K
9
=K2*4+1
。
所以K
9
可以表示为四个边不重的2因子之和，对于每个分 解出的因子的路径为：

P
i
v
i
v
i 1
v
i1
v
i2
v
i2
v
i3< br>v
in
v
in

则K
9
的四条路径为：
P
1
v
1
v< br>8
v
2
v
7
v
3
v
6
v< br>4
v
5
,
P
2
v
2
v
1
v
3
v
8
v
4
v
7
v
5
v
6
,
P
3
v
3
v
2
v
4
v
1
v
5
v
8
v
6
v
7
,
P
4
v
4
v
3
v
5
v
2
v
6
v
1
v
7
v
8
,
则生成圈H
i
是V
2n+1
与P
i
的两个端点连线生成的。所以可将K
9
表示为四个生成
圈之和。


5.13 所谓
nn
矩阵的一条对角线是指两两不同行不同列的n个矩阵
元 素组成的集。对角线的权是指它的n个元素的和。找出下列矩阵具
有最小权的对角线：
4

7


8


6

4
581011

6574


51296



613107

5798

解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4，
将其所在的 行和列删除，得到的矩阵为

6574


51296



613107


5798

再从此矩阵的第一 行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)
的4。依次类推，继续得到坐标是( 3,2)的5，(5,3)的7，(4,4)的10。
所以最小权为：4+4+5+7+10=30。