§4.3Hamilton图
* 经过图G的每个顶点恰一次的路称为G的Hamilton路。
* 经过图G的每个顶点恰一次的圈称为G的Hamilton圈。
Hamilton图的研究起源于十二面体的游戏（1856）
十二面体是H图 Herschel图不是H图
与Euler图不同，目前为止尚没有找到判别一个图是否是Hamilton图的有效充要条件。
这是图论中未解决的重要难题之一。
本节给出一些经典的充分条件和必要条件。
一、必要条件
定理4.3.1 设G是一个二部图，且有奇数个顶点，则G不是H图。（设G是二部图，若G
是H图，则G必有偶数个顶点）
证明： 留作习题。
*Herschel图是二部图，但有奇数个顶点，故不是H图。
定理 4.3.2 若G是H图，则对V(G)的每个非空真子集S，均有
W(G－S)≤ | S |。
证明：设C是G的H圈，则对V(G)的每个非空真子集S，均有
W(C－S)≤ | S |
由于C－S是G－S的生成子图，故W(G－S)≤W(C－S)≤ | S |.
证毕。
利用定理4.3.2可判断下面不是H图。
但定理4.3.2不能来判断下列Petersen图不是H图。
2. 充分条件
（1）度型条件
定理4.3.3(Dirac, 1952) 若G是简单图，且3≥ν，
2
ν
δ ≥，则G是Hamilton图。
证明 用反证法：假定定理不真。令
|{GA = G的顶点数为3≥ν，
2
ν
δ ≥，且G是非Hamilton图}。
取A中边最多的一个G。因3≥ν，故不是完全图（否则G是Hamilton图）。设u和v是G
的不相邻顶点。由G的选择，G＋uv是Hamilton图。因G是非Hamilton图，故G＋uv的H
圈必经过e = uv。于是G中存在以u为起点v为终点的Hamilton路
ν
vvv L
21
。这里uv =
1
，
vv =
ν
，令
}|{
1
EuvvS
ii
∈=
+
和}|{ EvvvT
ii
∈=。
由于TSv U?
ν
，故ν<|| TS U，并且0|| =TS I（因为若TSv
i
I∈?，则G将包含H
圈
11121
vvvvvvv
ii +?
LL
νν
，矛盾）。
故ν<+=+=+ ||||||||)()( TSTSTSvdud IU，这与
2
ν
δ ≥的前提矛盾。证毕。
(2) 闭包型条件
定理4.3.4（Bondy & Chvátal,1974） 设G是简单图，u和v是G中不相邻的顶点，且
ν≥+ )()( vdud，则G是Hamilton图当且仅当G＋uv 是Hamilton图。
证明：必要性是显然的。
充分性：若G＋uv是Hamilton图而G不是，则与定理4.3.3一样可推出矛盾。证毕。
定义：图G的闭包（closure）是指由如下方法所得之图：
反复连接G中度之和不小于ν的不相邻顶点对，直到没有这样的顶点对为止。
图G的闭包记为C(G)。
v
1 v2 v
3
v
i
v
i+1
v
v-1
v
v
……
u
v
v
1 v2 v
3
v
i
v
j
v
v-1
v
v
……
u
v
v
i+1
定理4.3.5 G的闭包C(G)是唯一确定的。
证明：设
21
,GG是按闭包构成方法所得的两个图。用
m
eee ,,,
21
L和
n
fff ,,,
21
L分别表示
在构作
21
,GG过程中给G添加边的序列。我们来证明每个
i
e一定是
2
G的边，而每个
j
f一
定是
1
G的边。
假设uve
k
=
+1
是序列
m
eee ,,,
21
L中第一条不属于
2
G的边，令
},,,{
21 k
eeeGH L+=。
由
1
G的定义知，ν≥+ )()( vdud
HH
。但因H是
2
G的子图，因此ν≥+ )()(
22
vdud
GG
。
而由
1+k
e的选择，u、v在
2
G中是不相邻的，这与
2
G是闭包矛盾。故每条
i
e都必是
2
G的边。
同理可证，每条
j
f一定是
1
G的边。这说明图G的闭包是唯一的。证毕。
例：
前一个图的闭包是它自己，后一个图的闭包是完全图K
5
。
定理4.3.6一个简单图是Hamilton图当且仅当它的闭包是Hamilton图。
证明：在构作闭包过程中，反复运用定理4.3.4即可。
推论4.3.1 设G是3≥ν的简单图。若C(G)是完全图，则G是Hamilton图。
定理4.3.2后的例子改动一条边后所得的如下图，可以检验它的闭包是完全图，因而是
Hamilton图。
（3）度序列条件
定理4.3.7 设G是度序列为（
ν
ddd ,,,
21
L）的简单图，这里
ν
ddd ≤≤≤ L
21
，并且3≥ν。
若不存在小于
2
ν
的m，使得md
m
≤和md
m
?<
?
ν
ν
，则G是Hamilton图。
证明：设G满足定理条件。我们来证明G的闭包C(G)是完全图。用反证法。
假设C(G)不是完全图。设u、v是C(G)中两个不相邻顶点，满足)()( vdud ≤，且)()( vdud +
尽可能大。（)(vd表示v在C(G)中的度）。由C(G)的定义，ν<+ )()( vdud。令
wuVwuN |}{\{)( ∈=在C(G)中与u不相邻};
wvVwvN |}{\{)( ∈=在C(G)中与v不相邻};
则)(1|)(| uduN ??=ν，)(1|)(| vdvN ??=ν。记mud =)(，则muN ??= 1|)(| ν，
1))((1)(1|)(| ?=???>??= mudvdvN ννν (1)
另外，由u、v的选择（)()( vdud +尽可能大）知，}{)( uuN U中每个顶点在C(G)中的度
不超过)(vd（否则，设)(uNv ∈′，)()( vdvd >′，则)()( vdud ′+ > )()( vdud +，当初
应当选择u和v′）。同理，N (v)中每个顶点在C(G)中的度不超过)(ud。结合（1）式可知：
C(G)中至少有m?ν个顶点，其度mvd ?<≤ ν)(，（比如}{)( uuN U中的顶点）；
C(G)中至少有m个顶点，其度m≤，（比如)(vN中的顶点）；
由于G是C(G)的子图，故上述结论对G也成立。按照度序列的排列方式，便有md
m
≤和
md
m
?<
?
ν
ν
，并且
2
ν
<m（因)()( vdud ≤及ν<+ )()( vdud）。这与定理的条件矛盾。
该矛盾说明C(G)确实是完全图。由推论4.3.1，G是Hamilton图。证毕。
§4.4旅行商问题(Travelling Salesman Problem,TSP)
问题：有n个城镇。一个旅行商从某一城镇出发，欲经过其余1?n个城镇一次且仅一次，
最后回到出发点。他应该如何设计旅行路线，才能使所走路程最短？
图论描述：将城镇作为顶点，两顶点连边当且仅当对应的两城镇能直达，每条边上以道路的
里程作为权。从而获得一个赋权图G。旅行商问题现在可以叙述为：
给定赋权图 G，求 G 的一个权最小的 Hamilton 圈。
这一问题看似简单，实际上含有两个困难的问题：
（1）如何判定G是否有Hamilton圈；
（2）在已知G是Hamilton图的情况下，如何求出一个权最小的Hamilton图来。
这两个问题目前尚未找到有效算法，甚至不知道这样的有效算法是否存在。事实上它们
是NPC问题。
转化：给G添加权为∞的边，化为赋权完全图。问题化为：对赋权完全图
n
K，求其最小权
Hamilton圈，这样的圈称为最小Hamilton圈。
在
n
K中，共有)!1(
2
1
?n个不同的Hamilton圈（v到其余顶点有1?n条边）。如果一
一计算各Hamilton圈的长度，再逐个比较出权最小的一个，则计算量太大。当n较大时无
法实现。
对这样的NPC问题，一般解决方法是设计较好的近似算法，求其近似最优解。下面介
绍三种求最优Hamilton圈的近似算法。
近似算法1－邻近点法
step1. 任选一点Vv ∈
1
，令1:,
11
== ivP。
Step2. 设已得到
ii
vvvP L
21
=，选取},,{211 ii
vvvVv L∈
+
使得权)(
1+ii
vvw最小。
Step3. 若ni =，则停止，
1211
vvvvvvPC
nnn
L=+=是一条近似的最小Hamilton圈；否
则1: += ii，转step2。
例
解：因5=n，故存在12!4
2
1
=×个不同的Hamilton圈。由计算可知abcdea，adcbea等是
最优解，权为36；而abdeca和acebda等是最差解，权为48。
按邻近点法来求：
比如从a点出发，可得四个近似解：abdeca，权为48；adbeca，权为48；aebdca，权
为41；aedbca，权为41。
如果从b出发，可得2个近似解：badecb，权为43，baedcb，权为36。
可见，邻近点法求近似解的精度不高，且与初始点有关。
定理4.4.1设赋权完全图
n
K各边的权均为正数，且权满足三角不等式：对于任意的
Vvvv
kji
∈,,，)()()(
kikjji
vvwvvwvvw ≥+，则
??
)1log(
2
1
2
0
+≤
?
n
c
c
。其中
?
c是
n
K的
最小Hamilton圈的权，而
0
c是用邻近点法求得的Hamilton圈的权。
证明较长，从略。
注：对精确算法需要证明其正确性；对近似算法需要估计算法的性能（精度）。
5
5
5
8
8
9
9
7 16
12
a
b
c d
e
近似算法2－最小生成树法
step1. 求
n
K的一棵最小生成树T；
step2. 将T中各边均添加一条重边，设所得图为
*
G；
step3. 求
*
G的从某点v出发的一条Euler环游
v
E；
step4. 按下面的方法求出G的一条Hamilton路：
从顶点v出发，沿E
v
访问G
*
中各顶点。在此过程中，一旦遇到重复顶点，就跳过它直接走
到Euler环游上的下一个顶点。直到访问完所有顶点为止。
该算法的计算复杂度为)(
2
νO。
例
G 最小生成树 加重边后
注：（1）若由不止一棵最小生成树，则最小生成树的选择会影响最重的结果（H圈的权）。
（2）Euler环游路线也影响最终结果。
（3）选择Euler环游的不同起点也影响最终的结果。
定理4.4.2设赋权完全图的各边之权均为正数，且对Vvvv
kji
∈? ,,，都有
)()()(
kijji
vvwvkvwvvw ≥+，则2
*
0
<
c
c
。这里
0
c是算法2所得的Hamilton圈H的权（近
似解）。而
*
c是最小Hamilton圈
*
H的权。
证明：设T，G
*
如算法所述。设E是G
*
中一条Euler环游。由于对Vvvv
kji
∈? ,,，都有
)()()(
kijji
vvwvkvwvvw ≥+，故)(2)()(
0
TwEwcHw =≤=。此外，设T′是G的最小
Hamilton圈
*
H删去任一边后所得的生成树，则
*
)()( cTwTw <′≤。因而
*
0
2cc <。证毕。
近似算法3－最小权匹配法（Christofides算法）
step1. 求完全图
n
K的一棵最小生成树T
step2. 设T 中奇度顶点的集合为},,,{
221 k
vvvV L=′。求V′的导出子图
k
KVG
2
][ =′的最
小权完美匹配，将得到的k条边添加到T上，得Euler图G
*
。
step3. 求出G
*
的从某顶点v出发的一条Euler环游
v
E。
5
5
5
8
8
9
9
7 16
12
a
b
c d
e
5
5
5
9
a
b
c d
e
5
5
5
9
a
b
c d
e
step4. 从v出发沿
v
E访问G
*
的各个顶点。在此过程中，一旦遇到重复顶点，就跳过它直接
走到Euler环游上的下一个顶点。直到访问完所有顶点为止。
例
G 最小生成树T ][VG ′ G
*
（][VG ′的最小完美匹配},{ cdaeM =，将M添加到T上，得G
*
。求G
*
中一条Euler环游，
然后按step4操作）。
定理4.4.3设赋权完全图的各边之权均为正数，且对Vvvv
kji
∈? ,,，都有
)()()(
kikjji
vvwvvwvvw ≥+，则
2
3
*
0
<
c
c
。这里
0
c是算法3所得的Hamilton圈H的权（近
似解），而
*
c是最小Hamilton圈
*
H的权。
证明：先证四条事实：
（1）
*
c去掉一条边后便得一生成树，故
*
)( cTw <。
（2）设
k
KVG
2
][ =′中最小权Hamilton图的权为c′。由于对Vvvv
kji
∈? ,,，都有
)()()(
kikjji
vvwvvwvvw ≥+，故)(
0 v
Ewc ≤。
（3）因][VG ′是完全图
n
K的子图，][VG ′的Hamilton圈可由
n
K的Hamilton圈通过“去
二添一”手续得到，故
*
cc ≤′。
（4）因][VG ′中最小Hamilton圈上交替取边可得一完美匹配，故][VG ′中最小权完美匹配
M中各边权之和
2
)(
c
Mw
′
≤。
由以上四条，得
*
*
*
0
2
3
2
)()()( c
c
cMwTwEwc
v
=+<+=≤。证毕。
5
5
5
8
8
9
9
7 16
12
a
b
c d
e
5
5
5
9
a
b
c d
e
16
5
5
a
c d
e12
8
9
5
5
5
9
a
b
c d
e
9
