-
哈密顿图判定
<
/p>
①
假设
G
?
(
V
,
E
)
是一个哈密顿图，则对
V
的任意非空子集
V
1
均有
W
(
G
?
V
1
)
?
< br>|
V
1
|
这里
G
?
V
1
表示从图
G
中删去
V
1
中的所有顶点以及所关联
的边；
W
(
G
?
V
1
)
表示
子
图
G
?
V<
/p>
1
的连通分支数。
证明：
因为图
G
是哈密顿图
所以必
存在哈密顿回路
C
。我们来考察一下两种情况
< br>
（
i
）
V
1
中的顶点在
C
中均彼此相邻，则
W
(
C
?
V
1
)
?
1
?
|
V
1
|
（
ii
）
V
1
中的顶点在
C
中不相邻，不妨设有
r
?
2
并且
r
?
|
V
< br>1
|
个顶点不相邻
则
W
(
C
?
V
1
)
?
r
?
|
V
1
|
< br>
一般情况下，
V
1
中的顶点在
C
中既有相邻的也有
不相邻的。
所以
<
/p>
W
(
C
?
V
1
)
?
|
V
1
|
而
C
?
V
1
是图
G
?
V
1
的生成子图<
/p>
所以
|
E<
/p>
(
C
?
V
1
)
|
?
|
E
(
G
?
V
1
)
|
所以，
W
(
G
?
V
1
)
?
W
(
C
?
V
1
)
?
|
V
< br>1
|
证毕
<
/p>
这是一个判定哈密顿图的必要条件，但它不充分。如果某一个图不满足
W
(
G
?
V
1
)
?
|<
/p>
V
1
|
，
则可以断定它不是哈密顿图。
②狄拉克定理：
如果图
G
是一个具有
n
(
n
?
3
)
个顶点的简单图，并且图<
/p>
G
中每个顶点
的度数至少为
n
，那么图
G
是哈密顿图。
2
Dirac
’
s theorem
：
If G
is a simple graph with n vertices with n
?
3 such that the degree of
every vertex in G is at least n/2,then
G has a Hamilton circuit.
狄拉克定理是英国数学家
G
．
A
．狄拉克（
Dirac
）在
1952
年给出的一个判定哈密顿图
的充分条件。
一般来讲都
是从简单图讨论。
因为对哈密顿图来讲每个顶点只能通过一次，
所
以如果图中出现自环和平行边，
那么对构造哈密顿图是没有什
么影响的，
因此，
只考虑简单
图即可。
证明：
假设
G
不是哈密顿图
在图
G
中连
接不相邻的两个顶点，所得到的图仍然满足定理的条件
（我们知道，当图
G
通过上述方法添加边，最终可以构造出一个完全图，而完
全图必定是哈密顿图）
因此通
过上述方法添加边，总可以使图
G
成为满足条件的极大非哈密顿
图。
这里不
妨设
G
就是极大非哈密顿图
（所谓极大非哈密顿图是指该图本
身不是哈密顿图，
但是在该图中，
任意一对不
< br>相邻的顶点之间加上一条边，它就成为哈密顿图。极大非哈密顿图肯定不是完全图）
从
G
中取两个不相邻的顶点
u
和
v
则
G
?
uv
必是哈密顿图，并且该哈密顿回路一定包含边
{
u
,
v
}
于是图
G
中一定存在一条从顶点
u
到顶点
v
的哈密顿通路（不是哈密顿回路）
u
?
v
1
v
2
v
3
...
v
n
?
v
令
S
?
{
v
i
|
{
v
1
v
i
?
1
}
< br>?
E
}
，
即
凡是与
v
1
邻接的顶点的前一个序号的顶点组成的集合
，
i
?
1
,
< br>2
,...,
n
?
1
-
-
-
-
-
-
-
-
-
上一篇：ARCGIS工具中英对照总结
下一篇：英语语篇教学