1
第四章 Euler 图和 Hamilton 图
§4.1 Euler 图
一、基本概念
通常认为，图论见诸于文献的起始研究之一是瑞士数学家欧拉关于七桥问题的研究。在
18 世纪普鲁士的哥尼斯堡城（ K?nigsberg）,普雷格尔（ Pregel）河穿城流过，河中有两个河心岛，有七座桥将小岛与河岸连接起来（如下图） 。有市民尝试从河岸或岛屿的任一陆地点出发，经过每座桥一次且仅一次回到出发点，但一直未能获得成功。人们怀疑，这样的走法是否存在？这便是七桥问题。
哥尼斯堡七桥 图 1
1741 年，欧拉经过对七桥问题的研究，发表了第一篇有关图论的论文，从而使七桥问题闻名于世。欧拉将四块陆地用平面上四个点来表示，两块陆地间有一座桥相连，就在两个相应的点间连一条边,最终获得如图 1 所示的一个图 G。 于是七桥问题转化为一个图论问题：
图 G 中从任一顶点出发，经过每条边恰好一次回到出发点，是否可能？
为了进一步的讨论，我们需要定义如下术语。
Euler 闭迹 (closed trail,tour,circuit)：经过图 G 的每条边恰好一次的闭迹。
Euler 迹 （ trail）,经过每条边恰好一次的迹。
Euler 图,有 Euler 闭迹的图。
利用这些术语，七桥问题可叙述为：图 1 中的图 G 是否为 Euler 图？欧拉对此做出了否定的回答。 事实上,欧拉研究了更一般的情况,获得了任意一个图是否为欧拉图的判定条件。
二,Euler 图的判定
定理 4.1.1 一个非空连通图是 Euler 图当且仅当它没有奇度顶点。
证明 必要性,设图 G 是 Euler 图,C 是 G 中一个 Euler 闭迹。对 )(GVv∈?,v 必在 C 上出现。 因 C 每经过 v 一次,就有两条与 v 关联的边被使用。 设 C 经过 v 共 k 次,则 kvd 2)( = 。
充分性,无妨设 1)( >Gν 。因 G 连通，故至少有一条边。下面用反证法证明充分性结论。
假设图 G 无奇度顶点，但它不是 Euler 图。令
S={G|G 至少有一条边，无奇度顶点，且不是 Euler 图 }
2
则 φ≠S 。取 S 中边数最少的一个，记为 G′。因 2)( ≥′Gδ,故 G′含有圈，因而含有闭迹。
设 C 是 G′中一条最长的闭迹。由假设,C 不是 G′的 Euler 闭迹。因此 )(\ CEG′ 必有一个连通分支至少含有一条边。记这个连通分支为
0
G 。由于 C 是闭迹，故
0
G 中没有奇度顶点，
且 )()(
0
GG ′<εε 。 由 G′的选择可知，
0
G 必有 Euler 闭迹
0
C 。 由于 G′连通,故 C 必经过
0
G
中至少一个顶点，从而 φ≠)()(
0
CVCV ∩ 。因此
0
CC + 是 G′ 的一条闭迹，且
)()(
0
CCC εε >+,这与 C 的选取矛盾。证毕。
充分性的另一种证法（数学归纳法）,
无妨设 1)( >Gν 。因 G 连通且无奇度顶点，故 2)( ≥Gδ,因而必含有圈。
当 2)( =Gν 时，设仅有的两点为 u,v，则 u,v 间必有偶数条边，它们显然构成 Euler 回路。
假设 kG =)(ν 时，结论成立。
当 1)( += kGν 时，任取 )(GVv∈ 。令 S = {v 的所有关联边 }。记 S 中的边为
m
eee null,,
21
，其中 )(vdm = 为偶数。记 vGG \=′ 。对 G′作如下操作,
（ 1） 任取 See
ji
∈,，设 vve
ii
=,vve
jj
= ；
（ 2）
ji
vvGG +′=′:,},{\:
ji
eeSS = ；
（ 3） 若 φ=S,则令 vGG?′=′:,停止；否则转（ 1）继续。
这个过程最终得到的 G′有 k 个顶点，且每个顶点在 G′中的度与在 G 中完全一样。由归纳假设,G′中有 Euler 闭迹，设为 P。将 P 中上述添加边
ji
vv 都用对应的两条边
ji
ee,代替，
显然获得 G 的一条 Euler 闭迹。证毕。
定理 4.1.2 一个连通图有 Euler 迹当且仅当它最多有两个奇度顶点。
证明 必要性,设连通图 G 有 Euler 迹 T，其起点和终点分别为 u,v。
若 )(GEuv∈,则 G 有 Euler 闭迹，由定理 4.1.1,G 无奇度顶点。
若 Guv?,则 uvG + 有 Euler 闭迹。由定理 4.1.1，图 uvG + 无奇度顶点。故 G 最多只可能有两个奇度顶点。
充分性,若 G 无奇度顶点，则由定理 4.1.1,G 有 Euler 闭迹，自然有 Euler 迹。
若 G 只有两个奇度顶点，设其为 u,v，则给 G 添加一条新边 uve = 所得的图 G +e 的每个顶点都是偶度顶点。从而 G +e 有 Euler 闭迹。故 G 有 Euler 迹。证毕。
一个图 G 如果有一条欧拉迹或欧拉闭迹，则我们可以沿着欧拉迹或欧拉闭迹连续而不重复地把 G 的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图，或者说它可一笔画成。如果图 G 可分解为两条迹或闭迹的并，则 G 的边可用两笔不重复地画完。同样地，如果图 G 可分解为 k 条迹或闭迹的并，则 G 可 k 笔画成。
3
定理 4.1.1 和定理 4.1.2 表明，一个图 G 可一笔画成的充分必要条件是 G 至多有 2 个奇度顶点。一般地，有下述推论。
推论 4.1.1 一个连通图可 k 笔画成当且仅当它最多有 2k 个奇度顶点。
证明留作习题。
Toida 于 1973 年发现，在一个欧拉图中，对任何一条边，经过它的圈的个数都是奇数。
1984 年,Mckee 又证明这个条件是充分的。这样便形成了对欧拉图的另一种刻画。
定理 4.1.3 一个非平凡连通图 G 是欧拉图的充分必要条件是 G 的每条边含在奇数个圈上。
证明：必要性：设 G 是欧拉图,则 G 的所有顶点都是偶数度的。任取 G 的一条边 e = uv,
因 G 有欧拉闭迹，故 GGe′=?是连通图。令 M 表示 G′中所有使顶点 u 恰好出现一次的不同的 u?v 迹组成的集合，这里两条迹相同是指两条迹的边数相同且每一步使用的边相同，
因此两条迹不同要么至少其中一条迹上有另一条迹所没有的边,要么两条迹使用边的次序不同。我们先来证明 M 含有奇数条迹。
从顶点 v 出发有奇数条边可作为迹的始边。一旦始边被确定，则这条迹就要继续到下一个顶点 w。由 于 除 vw 外 w 关联的边有奇数条，所以迹的第二条边有奇数种选择。如此继续，
直至到达迹的另一个端点 u。这表明始边使用 vw 的 u?v 迹有奇数条。对每一条始边都是如此，因此不同的 u?v 迹有奇数条。这里需要说明的是，如果迹中途重复经过某个顶点，上述递推过程仍然成立。
假设 T 是 G′中一条包含 u 恰好一次的 u?v 迹，但不是一条 u?v 路，则 T 必定重复经过了某些顶点，如果重复经过了顶点 v
1
，意味着 T 包含一条 v
1
v
1
闭迹 C，此时将 C“逆向”
使用,T 上其它边不变，便得到另一条 u?v 迹，我们称其为与 T 同类的 u?v 迹。可见，如果一条 u?v 迹重复经过 k 个点（多次经过的同一点的计重复经过次数）,则经这种逆向变换可获得 2
k
个同类 u?v 迹。这种分类构成一个等价关系，因此形成了对有重复点的 u?v 迹集合的划分。 划分出的每一个等价类有偶数个条 u?v 路。 这说明有重复点的 u?v 迹总共有偶数条。
有以上两方面知,GGe′=?中共有奇数条顶点不重复的 u?v 迹（即 u?v 路）,因此，
G 中共有奇数个含有边 e 的圈。
充分性：设 G 的每条边含在奇数个圈上，希望证明 G 的每个顶点都是偶数度的。任取顶点 v,设 v 关联的边共有 k 条，分别为
12
,,,
k
ee enull 。与这些边相应，构造一个有重边的图 H 如下,顶点集
12
H{,,,}
k
uu u= null,对于每个
i
u,相应于每个既含有
i
e 也含有某个
j
e 的圈，在
i
u 和
j
u 之间连一条边。
由于
i
e 含在奇数个圈上，且每个经过
i
e 的圈必经过
12
,,,
k
ee enull 中某条其它边，因此 H
中顶点
i
u 的度为奇数。 由
i
u 的任意性,H 中每个点的都是奇数。 由公式
1
2(H) ( )
k
i
i
duε
=
=
∑
知，
H 的顶点个数 k 必须是偶数，从而可知在 G 中顶点 v 关联偶数条边。由 v 的任意性,G 中所有点都是偶数度顶点，故为欧拉图。证毕。
4
三、求 Euler 图中的 Euler 闭迹－ Fleury 算法
对于复杂一些的图，即使判定出它有欧拉闭迹，也未必能很快地找出一条欧拉闭迹。在许多大规模应用中，需要借助于算法来找欧拉闭迹。 Fleury 给出了一个在欧拉图中找欧拉闭迹的多项式时间算法
[1]
。其基本思想是，从图中一个顶点出发，用深度优先方法找图的迹，
在任何一步，尽可能不使用剩余图的割边，除非没有别的选择。
[1] E,Lucas,Récréations Mathématiques IV,Paris,1921,
Fleury 算法的步骤如下,
输入：欧拉图 G
输出,G 的欧拉闭迹。
step1,任取 )(
0
GVv ∈,令
00
,vw =,0:=i 。
step2,设迹
iii
vevevw null
110
= 已取定。从 },,,{\
21 i
eeeE null 中选取一条边
1+i
e,使得
（ 1）
1+i
e 和
i
v 相关联；
（ 2）
1+i
e 不选 },,,{\
21 ii
eeeGG null= 的割边，除非没有别的选择。
step3,当 step2 不能再执行时，停止。
定理 4.1.3 若 G 是 Euler 图，则 Fleury 算法终止时得到的是 G 的 Euler 闭迹。
证明 设 G 是 Euler 图，
nnn
veevevW null
2110
= 是 Fleury 算法终止时得到的迹。则显然
n
v 在
},,,{\
21 nn
eeeGG null= 中的度数是 0（ 因算法终止在
n
v,若不是 0，则算法应继续 ） 。故
n
vv =
0
（ 否则
n
v 在 G 中是奇度顶点，这不可能 ）,即
n
W 是闭迹。
若
n
W 不是 G 的 Euler 闭迹，设 S = {
n
G 中度 >0 的所有顶点 }。则 φ≠S （因
n
W 不是 G
的 Euler 闭迹，有边不在
n
W 上）,且
n
W 上有 S 中的点（ 否则
n
G 中
n
W 上的点都是
n
G 的孤立点,这与 G 是 Euler 图 （从而连通） 矛盾 ）,但 SGVSv
n
\)(=∈ 。 设 m 是
n
W 上使得 Sv
m
∈
而 Sv
m
∈
+1
的最大整数。因
n
W 终止于 SGVS \)(=,故
11 ++
=
mmm
vve 是
m
G 中 ],[ SS 的仅有的一条边，因而是
m
G 的一条割边。
设 e 是
m
G 中和
m
v 关联的另一条边（ 因 0)( >
mG
vd
n
，这样的边 e 一定存在 ）,则由算法第二步知,e 必定也是
m
G 的一条割边 （ 否则,按算法应选 e 而不选
1+m
e ）,因而 e 是 ][SG
m
的割边。
S S
v
0
= v
n
v
m
e e
m+1
v
m+1
5
但由于
n
W 是闭迹,Svv
n
∈=
0
，且对 Sv∈?,)(vd
G
是偶数。故 ][SG
m
= []
n
GS中每个顶点都是偶数度顶点，由此又推出 ][SG
m
无割边（第二章习题 11） 。
以上两方面矛盾。证毕。
Fleury 算法的计算复杂度分析留给读者。
§ 2.中国邮递员问题（ Chinese Postman Problem）
中国邮递员问题（管梅谷,1960）,一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。请为他选择一条路线，使其所行路程尽可能短。
图论模型,求赋权连通图中含所有边的权最小的闭途径。这样的闭途径称为 最优回路 。
算法思想,（ 1）若 G 是 Euler 图，则 G 的 Euler 闭迹便是最优回路，可用 Fleury 算法求得；
（ 2）若 G 不是 Euler 图，则含有所有边的闭途径必须重复经过一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边的权相等）,最终消除了奇度顶点形成一个 Euler 图。因此，在这种情况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到 Euler 图
*
G,使得添加边的权之和
∑
∈Fe
ew )( 最小,（其中 )(\)(
*
GEGEF = ） ；然后用 Fleury 算法求
*
G 的一条 Euler
闭迹。这样便得到 G 的最优回路。
问题是：如何给图 G 添加重复边得到 Euler 图
*
G,使得添加边的权之和
∑
∈Fe
ew )( 最小？
方法 一（图上作业法）
定理 4.2.1 设 C 是一条经过赋权连通图 G 的每条边至少一次的回路，则 C 是 G 的最优回路当且仅当 C 对应的欧拉图
*
G 满足,
（ 1） G 的每条边在
*
G 中至多重复出现一次；
（ 2） G 的每个圈上在
*
G 中重复出现的边的权之和不超过该圈总权的一半。
证明 必要性：先证（ 1）
设 C 是最优回路，即 C 是它所对应的
*
G 的一个 Euler 闭迹。假设 G 中的边 uve = 被 C
经过了 m 次，即在
*
G 中 u,v 之间有 m 条重边。若 3≥m,则在
*
G 中删去这 m 条边中的两条，不改变 u,v 的度数的奇偶性。所得图 G′仍为 Euler 图，但 )()(
*
GwGw <′,即 G′中的欧拉闭迹是比 C 更优的一条投递路线，这是矛盾的。
下证（ 2） 。
设
1
C 是 G 中一个圈，且在
*
G 中，
1
C 上重复出现的边的权之和 >
1
C 的权的一半。将
1
C
上重复的边改为不重复而未重复的边改为重复边。
6
这样做不改变
*
G 中
1
C 上各顶点的度数的奇偶性。设所得图为 G
~
，则 G
~
仍是欧拉图，但
)()
~
( GwGw <,G
~
的欧拉闭迹比 C 更优。这是不可能的。
充分性,设
1
C 是 G 的一条投递路线 （经过每条边至少一次的回路）,它对应的欧拉图
*
1
G
满足（ 1）和（ 2） 。设
2
C 是 G 的一个最优回路，我们来证明
12
() ()wC wC= 。
设
*
2
G 是
2
C 对应的欧拉图（由必要性知，
*
2
G 满足（ 1）和 (2)）,
1
F,
2
F 分别为
*
1
G 和
*
2
G
的重复边集合。令 )(\)(
2121
FFFFF ∩∪=,而 [F]为 F 在
*
2
*
1
GG ∪ 中的导出子图（ [F]
中的边全是
1
F 和
2
F 的边，且无一边既在
1
F 中又在
2
F 中） 。
由于在
*
1
G 和
*
2
G 中，给一个顶点 v 添加边的条数的奇偶性与度数 )(vd
G
的奇偶性相同，
故 [F]中各顶点的度数均为偶数。这表明 [F]各连通分支均为欧拉图。从而 [F]是若干个圈的边不重的并。而且 [F]中各圈均既有
1
F 的边又有
2
F 的边（因
1
F 的边不会形成圈，
2
F 的也是） 。
由条件（ 2）,[F]中任一个圈 C′上
1
F 的边的权之和与
2
F 的边的权之和均不超过 )(
2
1
Cw ′ 。
于是
1
F,
2
F 在 C′上边的权之和必都等于 )(
2
1
Cw ′ 。这说明 [F]中属于
1
F 的边的权之和＝ [F]
中属于
2
F 的边的权之和。因此 )()(
*
1
*
2
GwGw =,从而 )()(
12
CwCw = 。
证毕。
奇偶点图上作业法,
先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。
奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，
计算量很大，实际当中用得较少。
方法二（ Edmonds-Johnson 方法）
定理 4.2.2 设 G 是赋权连通图,G 中有 k2 个奇度顶点。设
,|{ EeeA ∈= 在求最优回路时 e 被添加重复边 }。
则 G[A]是以 G 的奇度顶点为起点和终点的 k 条无公共边的最短路之并。
该定理的证明较长，有兴趣的读者可参看文献 [2]。
F
2
F
1
E(G
2
*
)
E(G
1
*
)
E(G)
7
基于此定理,Edmonds 和 Johnson 于 1973 年给出了求解邮递员问题的一个有效算法
[2]
。
Edmonds-Johnson 算法,
Step1,若 G 中无奇度顶点，令 GG =
*
，转 step2；否则转 step3。
Step2,求 G
*
中的 Euler 回路，结束。
Step3,求 G 中所有奇度顶点对之间的最短路。
Step4,以 G 中奇度顶点集 V′ 为顶点集，构作赋权完全图 |)|(,VnK
n
′=,使得对
Vvv
ji
′∈?,，
n
K 中边
ji
vv 的权为
i
v 至
j
v 在 G 中最短路的权。
Step5,求
n
K 中最小权完美匹配 M。
Step6,将 M 中边对应的各最短路中的边在 G 中加重复边，得 Euler 图 G
*
，转 step2。
注,该算法的复杂度为 )(
2
νO 。
例 4.2.1 求下图 G 的最优投递路线,A 为邮局。
解,G 只有两个奇点,},{ EBV =′ 。 B 到 E 的最短路为 BAFE，权为 13。完全赋权图
2
K 及相应的 Euler 图 G
*
为
易求得其 Euler 闭迹，并得到最优回路。
有关欧拉图和中国邮递员问题的更多内容可参看文献
[2] J,Edmonds and E.L,Johnson,Matching,Euler tours and the Chinese postman,Mathematical
Programming,5(1973) 88-124,
[3] H,Fleischner,Eulerian graphs,in Selected Topics in Graph Theory II (L,W,Beineke,and R.J,
Wilson eds.),Academic Press,London,(1983) 17-54,
[4] N,Christofides,Graph Theory-An Algorithmic Approach,Academic Press,Inc.,New York,
1990,
[5] G,Chartrand,and O.R,Oellermann,Applied and Algorithmic Graph Theory,McGraw-Hill,
Inc.,New York,1993,
[6] 谢政，网络算法与复杂性理论（第二版）,国防科技大学出版社,2003 年。
[7]H,Hamers,P,Borm,R Van de Leensel,and S,Tijs,Cost allocation in the Chinese postman
problem,Eur,J,Oper,Res.,118(1999) 153-163,
[8] D,Granot,H,Hamers,On the equivalence between some local and global Chinese postman
and traveling salesman graphs,Discrete Applied Mathematics,134(2004),67-76,
A
F
E
D
CB
4
3
10
14
8
5
6
5
9
E B
13
A
F
E
D
CB
4
3
10
14
8
5
6
5
9
G
*
K
2
8
§ 4.3Hamilton 图
定义 4.3.1 经过图 G 的每个顶点恰一次的路称为 G 的 Hamilton 路,简称为 H 路。经过图 G
的每个顶点恰一次的圈称为 G 的 Hamilton 圈,简称为 H 圈。具有 Hamilton 圈的图称为
Hamilton 图,简称为 H 图。
Hamilton 图的研究起源于一种十二面体上的游戏。 1857 年，爱尔兰著名数学家 William
Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体,在正十二面体的每个顶点上有一个木栓,并标有世界著名城市的名字。
游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。这个游戏当时称为 Icosian 游戏，也称为周游世界游戏。
将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。
周游世界游戏用图论术语来说就是判断十二面体图是否 Hamilton 图,并设法找出其 Hamilton
圈。其中一条 Hamilton 圈如图中粗边所示。
十二面体图是 H 图
判断一个图是否 Hamilton 图与判断一个图是否 Euler 图似乎很相似,然而二者却有本质的不同。目前为止尚没有找到判别一个图是否是 Hamilton 图的有效充要条件。这是图论和计算机科学中未解决的重要难题之一。
本节给出一些经典的充分条件和必要条件。
一、必要条件
定理 4.3.1 设 G 是二部图，若 G 是 H 图，则 G 必有偶数个顶点。
证明：设 G = (X,Y ),由于 G 的边全在 X 和 Y 之间，因此如果 G 有 Hamilton 圈 C，则 G
的所有顶点全在 C 上,且必定是 X 的点和 Y 的点交替在 C 上出现,因此 G 必有偶数个顶点。
证毕。
这个定理给出了一个二部图不是 Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是 Hamilton 图。例如，下列 Herschel 图是二部图，但有奇数个顶点，
故不是 H 图。
Herschel 图不是 H 图
9
定理 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 可判断下面 (1)中的图不是 H 图。事实上，令 S={u,v,w}，则
W(G－ S) = 4 > | S |。
但无法用该定理给出的必要条件来判断 (2)中的 Petersen 图不是 H 图。
二、充分条件
（ 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 null
21
。
这里 uv =
1
,vv =
ν
，令
}|{
1
EuvvS
ii
∈=
+
和 }|{ EvvvT
ii
∈= 。
由于 TSv ∪?
ν
，故 ν<|| TS ∪,并且 0|| =TS ∩ （因为若 TSv
i
∩∈?,则 G 将包含 H
圈
11121
vvvvvvv
ii +?
nullnull
νν
，矛盾） 。
故 ν<+=+=+ ||||||||)()( TSTSTSvdud ∩∪,这与
2
ν
δ ≥ 的前提矛盾。证毕。
u
v w
（ 1）
（ 2）
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
10
(2) 闭包型条件
Ore 注意到，上述 Dirac 定理的证明过程中，条件
2
ν
δ ≥ 仅仅用来证明对不相邻顶点
u,v，有 ν≥+ )()( vdud 成立。因此可以将图存在 Hamilton 圈的条件由
2
ν
δ ≥ 弱化为
ν≥+ )()( vdud 。这样便得到下述定理。
定理 4.3.4（ Ore,1960）
[1]
设 G 是简单图,u 和 v 是 G 中不相邻的顶点,且 ν≥+ )()( vdud,
则 G 是 Hamilton 图当且仅当 G＋ uv 是 Hamilton 图。
证明：必要性是显然的。
充分性：若 G＋ uv 是 Hamilton 图而 G 不是，则与定理 4.3.3 一样可推出矛盾。证毕。
Bondy 和 Chvátal 用更一般的形式表述了 Ore 观察到的实质，得到了图存在长度为 k
的圈和其它子图的充分条件 ( k υ= 时便是 Hamilton 圈 )
[2]
。他们用到了闭包的概念。
定义,图 G 的 闭包 （ closure） 是指由如下方法所得之图：反复连接 G 中度之和不小于 ν 的不相邻顶点对，直到没有这样的顶点对为止。图 G 的闭包通常记为 C(G)。
例如，对下列两图，前一个图的闭包是它自己，后一个图的闭包是完全图 K
5
。
定理 4.3.5 G 的闭包 C(G)是唯一确定的。
证明：设
21
,GG 是按闭包构成方法从 G 所得的两个闭包。用
m
eee,,,
21
null 和
n
fff,,,
21
null 分别表示在构作
21
,GG 过程中给 G 添加边的序列。我们用反证法来证明每个
i
e 一定是
2
G 的边，且每个
j
f 一定是
1
G 的边。
假设
m
eee,,,
21
null 中有不属于
2
G 的边，取序列中第一条不属于
2
G 的边设为 uve
k
=,
令
},,,{
121?
+=
k
eeeGH null 。
由
1
G 的定义知,ν≥+ )()( vdud
HH
。但 H 也是
2
G 的子图，因此由 ν≥+ )()( vdud
HH
知
ν≥+ )()(
22
vdud
GG
。而由
k
e 的选择,u,v 在
2
G 中是不相邻的，这与
2
G 是闭包矛盾。故每条
i
e 都必是
2
G 的边。
同理可证，每条
j
f 一定是
1
G 的边。这说明图 G 的闭包是唯一的。证毕。
定理 4.3.6（ Bondy & Chvátal,1976）
[2]
一个简单图是 Hamilton 图当且仅当它的闭包是
Hamilton 图。
证明：在构作闭包过程中，反复运用定理 4.3.4 即可。证毕。
11
根据该定理，下一个结论是显然的。
推论 4.3.1 设 G 是 3≥ν 的简单图。若 C(G)是完全图，则 G 是 Hamilton 图。
定理 4.3.2 后的例子改动一条边后所得的如下图，可以检验它的闭包是完全图，因而是
Hamilton 图。
（ 3）度序列条件
Chvátal 发现，如果图 G 满足：若有某些顶点的度比较小，则就有相应另一些顶点的度足够大,那么 G 就会成为 Hamilton 图。 具体来说,设简单图 G 的顶点度为
12
dd d
υ
≤≤≤null,
如果对任意正整数
2
m
υ
<,要么
m
dm>,要么
m
dm
υ
υ
≥?，则 G 是 Hamilton 图。这个结论正式叙述如下。
定理 4.3.7 (Chvátal,1972)
[3]
设 G 至少含有 3 个顶点的简单图，其度序列为 (
12
,,,dd d
υ
null )，
这里
12
dd d
υ
≤≤≤null 。若不存在小于
2
υ
的 m 使得 md
m
≤ 和
m
dm
υ
υ
<? 同时成立，则
G 是 Hamilton 图。
证明：设 G 满足定理条件。我们来证明 G 的闭包 C(G)是完全图。用反证法。
假设 C(G)不是完全图。设 u,v 是 C(G)中两个不相邻顶点，满足 )()( vdud ≤,且
)()( vdud + 尽可能大。 （ )(vd 表示 v 在 C(G)中的度） 。由 C(G)的定义,() ()du dv υ+<。
令
wuVwuN |}{\{)( ∈= 在 C(G)中与 u 不相邻 };
wvVwvN |}{\{)( ∈= 在 C(G)中与 v 不相邻 };
则 |()| 1 ()Nu duυ=,|()| 1 ()Nv dvυ= 。记 mud =)(,则 |()| 1Nu mυ=,
|()| 1 () 1( () 1Nv dv du mυυυ= > =? (1)
另外，由 u,v 的选择（ )()( vdud + 尽可能大）知,}{)( uuN ∪ 中每个顶点在 C(G)中的度不超过 )(vd （否则，设 )(uNv ∈′,)()( vdvd >′,则 )()( vdud ′+ > )()( vdud +,当初应当选择 u 和 v′） 。同理,N (v)中每个顶点在 C(G)中的度不超过 )(ud 。结合（ 1）式可知,
C(G)中至少有 m?ν 个顶点，其度 mvd?<≤ ν)(,（比如 }{)( uuN ∪ 中的顶点） ；
C(G)中至少有 m 个顶点，其度 m≤,（比如 )(vN 中的顶点） ；
12
由于 G 是 C(G)的子图，故上述结论对 G 也成立。按照度序列的排列方式，便有 md
m
≤ 和
md
m
<
ν
ν
，并且
2
ν
<m （因 )()( vdud ≤ 及 ν<+ )()( vdud ） 。这与定理的条件矛盾。
该矛盾说明 C(G)确实是完全图。由推论 4.3.1,G 是 Hamilton 图。证毕。
关于 Hamilton 图的更多结果可参看 [4],[5]
[1] O.Ore,Noye on Hamilton circuits,Amer,Math,Monthly,67(1960),55,
[2] J.A,Bondy,and V,Chvátal,A method in graph theory,Discrete Mathematics,15(1976),
111-136
[3] V,Chvátal,On Hamilton’s ideals,J,Combinatorial Theory (B),12(1972),163-168,
[4] V,Chvátal,Hamiltonian cycles,in The Traveling Salesman Problem,A Guided Tour of
Combinatorial Optimization (ed,E.L,Lawler,J.K,Lenstra,A.H.G,Rinnooy Kan,D.B,Shmoys),
Wiley,(1985),403-429,
[5] J.-C,Bermond,Hamiltonian graph,in Selected Topics in Graph Theory (L,W,Beineke,and
R.J,Wilson eds.),Academic Press,London,(1978) 127-168
§ 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 圈的近似算法。
13
近似算法 1－邻近点法
step1,任选一点 Vv ∈
1
，令 1:,
11
== ivP 。
Step2,设已得到
ii
vvvP null
21
=,选取 },,{\
211 ii
vvvVv null∈
+
使得权 )(
1+ii
vvw 最小。
Step3,若 ni =,则停止，
1211
vvvvvvPC
nnn
null=+= 是一条近似的最小 Hamilton 圈；否则 1,+= ii,转 step2。
例 4.4.1 求如下赋权完全图的最小权的 Hamilton 圈。
解：因 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 圈的权。
证明较长，从略。
近似算法 2－最小生成树法
step1,求
n
K 的一棵最小生成树 T；
step2,将 T 中各边均添加一条重边，设所得图为
*
G ；
step3,求
*
G 的从某点 v 出发的一条 Euler 闭迹
v
E ；
step4,按如下方法求出 G 的一条 Hamilton 路：从顶点 v 出发，沿 E
v
访问 G
*
中各顶点。在此过程中，一旦遇到重复顶点，就跳过它直接走到 Euler 环游上的下一个顶点。直到访问完所有顶点为止。
例 4.4.2 用最小生成树法求如下赋权完全图的最小权 Hamilton 圈。
解,求解过程图示如下。先求出一棵最小生成树 T,T 的各边加重边后得 G
*
,G
*
从 a 点出
5
5
5
8
8
9
9
7 16
12
a
b
c d
e
14
发的一条 Euler 闭迹为 C = aeadabcba，从 a 点出发沿 C 依次访问各点，遇到已访问过的点时直接跳到 C 的下一个点，这样便得到近似的最小权 Hamilton 圈 aedcba。
注,（ 1）若由不止一棵最小生成树，则最小生成树的选择会影响最终的结果 (H 圈的权 )。
（ 2） Euler 闭迹路线也影响最终结果。
（ 3）选择 Euler 闭迹的不同起点也影响最终的结果。
定理 4.4.2 设赋权完全图的各边之权均为正数，且对 Vvvv
kji
∈?,,，都有
()( ) ()
ij jk ik
wvv wvv wvv+≥，则 2
*
0
<
c
c
。这里
0
c 是算法 2 所得的 Hamilton 圈 H 的权（近似最优值）,而
*
c 是最小 Hamilton 圈
*
H 的权。
证明：设 T 和 G
*
如算法所述。设 E 是 G
*
中一条 Euler 闭迹。由于对 Vvvv
kji
∈?,,，都有
)()()(
kikjji
vvwvvwvvw ≥+,故 )(2)()(
0
TwEwcHw =≤= 。此外，设 T′是 G 的最小
Hamilton 圈
*
H 删去任一边后所得的生成树，则
*
)()( cTwTw <′≤ 。因而
*
0
2cc < 。证毕。
近似算法 3－最小权匹配法 (Christofides 算法 )
[ 1]
step1,求完全图
n
K 的一棵最小生成树 T
step2,设 T 中奇度顶点的集合为 },,,{
221 k
vvvV null=′ 。求 V′的导出子图
k
KVG
2
][ =′ 的最小权完美匹配，将得到的 k 条边添加到 T 上，得 Euler 图 G
*
。
step3,求出 G
*
的从某顶点 v 出发的一条 Euler 闭迹
v
E 。
step4,从 v 出发沿
v
E 访问 G
*
的各个顶点。在此过程中，一旦遇到重复顶点，就跳过它直接走到 Euler 闭迹上的下一个顶点。直到访问完所有顶点为止。
[1] N,Christofides,Worst-case analysis of a new heuristic for the traveling salesman problem,
Technical Report,Graduate School of Industrial Administration,Carnegie-Mellon University,
Pittsburgh,PA(1976),
例 4.4.3 用 Christofides 法求如下赋权完全图的最小权 Hamilton 圈。
解,求解过程图示如下。先求出一棵最小生成树 T，再求出 T 中奇度顶点集合 V′={a,c,d,e}
在 G 中导出的子图 []GV′,并求出 []GV′ 的最小权完美匹配 {ae,cd}。将这两条匹配边添加到 T 上，得 Euler 图 G
*
。 G
*
从 a 点出发的一条 Euler 闭迹为 C = aeadcba，从 a 点出发沿 C
依次访问各点，遇到已访问过的点时直接跳到 C 的下一个点，这样便得到近似的最小权
Hamilton 圈 aedcba。
G
最小生成树 T 加重边后得 G
*
近似最优 H 圈
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
5
5
8
9
a
b
c d
e
9
15
G 最小生成树 T ][VG ′ G
*
定理 4.4.3 设赋权完全图的各边之权均为正数，且对 Vvvv
kji
∈?,,，都有
)()()(
kikjji
vvwvvwvvw ≥+,
则
2
3
*
0
<
c
c
。 这里
0
c 是算法 3 所得的 Hamilton 圈 H 的权 (近似最优值 )，而
*
c 是 G 的最小
Hamilton 圈
*
H 的权。
证明：先证四条事实,
（ 1）
*
H 去掉一条边后便得一生成树，故
*
)( cTw < 。
（ 2）由于对 Vvvv
kji
∈?,,，都有 )()()(
kikjji
vvwvvwvvw ≥+,故 )(
0 v
Ewc ≤ 。
（ 3）设
k
KVG
2
][ =′ 中最小权 Hamilton 圈的权为 c′。因 ][VG ′ 是完全图
n
K 的子图,][VG ′
的 Hamilton 圈可由
n
K 的 Hamilton 圈通过“去二添一”手续得到，故
*
cc ≤′ 。
（ 4）因 ][VG ′ 中最小 Hamilton 圈上交替取边可得 ][VG ′ 的一个完美匹配，故 ][VG ′ 中最小权完美匹配 M 中各边权之和
2
)(
c
Mw
′
≤ 。
由以上四条，得
*
*
*
0
2
3
2
)()()( c
c
cMwTwEwc
v
=+<+=≤ 。证毕。
TSP 问题是一个内容十分丰富而又非常活跃的研究方向。有关 TSP 问题的进一步了解可参看 [7]~[9]，有关 TSP 问题算法的新进展可参看 [10]~[18]
[7] E.L,Lawler,J.K,Lenstrar,A.H.G,Rinnooy and D.B,Shmoys,The Traveling Salesman
Problem,New York,Wiley-Interscience,1986,
[8] N,Christofides,Graph Theory-An Algorithmic Approach,Academic Press,Inc.,New York,
1990,
[9] G,Chartrand,and O.R,Oellermann,Applied and Algorithmic Graph Theory,McGraw-Hill,
Inc.,New York,1993,
[10] S,Arora,Polynomial time approximation schemes for Euclidean TSP and other geometric
problems,Proceedings of 37
th
Annual Sym,Foundation of Computer Science,Oct,1996,
[11] S,Arora,Nearly linear time approximation schemes for Euclidean TSP and other geometric
problems,Proceedings of 38
th
Annual Sym,Foundation of Computer Science,Oct,1997,
[12] D,Applegate,R,Bixby,On the Solution of traveling salesman problems,Documenta
Mathematica J,DMV,Extra Volume ICM 1998 III,(1998) 645-656,
[13] C.S.Mata and J.Mitchell,Approximation algorithms for Geometric tour and network
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
16
problems,in Proceeding of 11
th
ACM Symposium on Computing Geomrtry,1995,360-369,
[14] G,Reinelt,TSPLIB-A traveling salesman problem library,ORSA J,Computing,3(1991)
376-384,
[15] J,Bentley,Fast algorithms for geometric traveling salesman problem,ORSA J,on Computing,
4(1992) 387-411,
[16] E,Lawler,J.K,Lenstra,A,Rinnooy Kan,D,Shmoys(eds.),The Traveling Salesman Problem,
Wiley,UK,1989,
[17] J.Potters,I,Curiel,S,Tijs,Traveling salesman games,Math,Programming,53(1992)
199-211,
[18] D,Granot,H,Hamers,On the equivalence between some local and global Chinese postman
and traveling salesman graphs,Discrete Applied Mathematics,134(2004),67-76,
第四章习题
1,证明：一个连通图可 k 笔画完当且仅当它最多有 2k 个奇度顶点。
2,若 G 是 Euler 图，则 G 的每个块也是 Euler 图。
3,确定 m 和 n 的值是的完全二部图
,
K
mn
是欧拉图。
4,证明或否定,（ 1）每个欧拉二部图有偶数条边； （ 2）含偶数个顶点的每个欧拉简单图哟偶数条边。
5,是否存在偶数个顶点、奇数条边的欧拉图？若不存在，给出理由；若存在，举出例子。
6,图 G 是欧拉图的充分必要条件是 G 可表成无公共边的圈的并。
7,下列两图是否分别可以一笔画？若可以，找出画法；若不可以，说明理由。
8,判断 Herschel 图和 Petersen 图分别能几笔画成。
9,给出一个算法，用以在有欧拉迹的图中求一条欧拉迹。
10,判断下图 1 是否 Euler 图。若是，用 Fleury 算法求其一个 Euler 环游。
G
1
G
1
Herschel 图 Petersen 图
17
11,求图 2 的一条最优邮路。
12,多米诺骨牌每一块上有 0,1,2,3,4,5,6 七个数字之一（ 0 用 O 表示，其它数字用点数表示） 。将标有不同数字的多米诺骨牌组成骨牌对子，如 (0,1),(2,4)等（无序对）,
共可组成
76
21
2
×
= 个不同的对子。现要将这 21 个对子首尾相接连起来，使得对任何两个相邻的对子，前一个对子的尾数与后一个对子的首数相等，问是否能按此规则将之 21
个骨牌对子连成一个圆圈？
13,用丝线将 mn× 个珍珠穿成一个网（如图）,现在想将一些丝线段剪断，得到一个由这些珍珠做成的项链，问 m 和 n 应满足什么条件？
14,判断下列图形是否 Hamilton 图，若是，找出一条 Hamilton 圈；若不是，说明理由。
15,设 G 是二部图 G=(X,Y)。若 |X|≠ |Y|,则 G 不是 Hamilton 图。
16,证明 Petersen 图不是 Hamilton 图（图见题 7） 。
17,给出一种方法，将完全二部图 K
n,n
分解为
2
n
个两两无公共边的 Hamilton 圈的并。
18,证明：若 G 不是 2－连通图，则 G 不是 Hamilton 图。
19,设 2k ≥,证明顶点数为 2k?1 的 k 次正则图是 Hamilton 图。
20,若图 G 的任二顶点间有 Hamilton 路，则称 G 是 Hamilton 连通图。证明,G 是 Hamilton
连通图且 (G) 4υ ≥,则
31
(G)
2
υ
ε
+
> 。
21,若 G 有 Hamilton 路，则对 V(G)的每个真子集 S，有 W(G – S)≦ |S|+1。
图 1 图 2
9
68
4
3
F
9
5
7
E
DB
C
A
18
22,证明：简单图 G 有 Hamilton 路当且仅当 G + K
1
有 Hamilton 圈。
23,设简单图 G 的度序列为
12
dd d
υ
≤≤≤null 。证明：若对任意正整数
1
2
m
υ +
<,要么
m
dm>,要么
1m
dm
υ
υ
+
≥?，则 G 有 Hamilton 路。
24,设 G 是一个简单图,(G) 3υ ≥,如果对满足 1
2
m
υ
≤ ≤ 的任意正整数 m，度不超过 m
的顶点个数比 m 小，则 G 是 Hamilton 图。
25,教室里有 6 排椅子，每排 5 张椅子，每张椅子坐一名学生。现在班主任老师考虑每周调整一次学生们的座位，使得每个学生都调到本次调整前与他相邻的某个座位上（前后左右视为相邻）,一个学期内每个学生都不能调回到他已经坐过的座位上。请帮老师制定一个调整方案。如果老师现在改变了主意，希望每次将每个学生调到原先与他不相邻的某个座位上，问是否可行？应怎样调整？
26,若围一张圆桌坐着至少 6 个人，那么一定可以调整他们的位置，使得每个人两侧都挨着新邻居。
27,某楼层的平面结构示意图如下。试说明从前门进去经过每个门口恰好一次且从后门出去是不可能的。
28,一个博物馆称为设计良好的，如果存在经过每个房间恰好一次的参观路线。某博物馆的楼层平面设计如下图，试证明这个博物馆的设计不是良好的。
后门前门
第四章 Euler 图和 Hamilton 图
§4.1 Euler 图
一、基本概念
通常认为，图论见诸于文献的起始研究之一是瑞士数学家欧拉关于七桥问题的研究。在
18 世纪普鲁士的哥尼斯堡城（ K?nigsberg）,普雷格尔（ Pregel）河穿城流过，河中有两个河心岛，有七座桥将小岛与河岸连接起来（如下图） 。有市民尝试从河岸或岛屿的任一陆地点出发，经过每座桥一次且仅一次回到出发点，但一直未能获得成功。人们怀疑，这样的走法是否存在？这便是七桥问题。
哥尼斯堡七桥 图 1
1741 年，欧拉经过对七桥问题的研究，发表了第一篇有关图论的论文，从而使七桥问题闻名于世。欧拉将四块陆地用平面上四个点来表示，两块陆地间有一座桥相连，就在两个相应的点间连一条边,最终获得如图 1 所示的一个图 G。 于是七桥问题转化为一个图论问题：
图 G 中从任一顶点出发，经过每条边恰好一次回到出发点，是否可能？
为了进一步的讨论，我们需要定义如下术语。
Euler 闭迹 (closed trail,tour,circuit)：经过图 G 的每条边恰好一次的闭迹。
Euler 迹 （ trail）,经过每条边恰好一次的迹。
Euler 图,有 Euler 闭迹的图。
利用这些术语，七桥问题可叙述为：图 1 中的图 G 是否为 Euler 图？欧拉对此做出了否定的回答。 事实上,欧拉研究了更一般的情况,获得了任意一个图是否为欧拉图的判定条件。
二,Euler 图的判定
定理 4.1.1 一个非空连通图是 Euler 图当且仅当它没有奇度顶点。
证明 必要性,设图 G 是 Euler 图,C 是 G 中一个 Euler 闭迹。对 )(GVv∈?,v 必在 C 上出现。 因 C 每经过 v 一次,就有两条与 v 关联的边被使用。 设 C 经过 v 共 k 次,则 kvd 2)( = 。
充分性,无妨设 1)( >Gν 。因 G 连通，故至少有一条边。下面用反证法证明充分性结论。
假设图 G 无奇度顶点，但它不是 Euler 图。令
S={G|G 至少有一条边，无奇度顶点，且不是 Euler 图 }
2
则 φ≠S 。取 S 中边数最少的一个，记为 G′。因 2)( ≥′Gδ,故 G′含有圈，因而含有闭迹。
设 C 是 G′中一条最长的闭迹。由假设,C 不是 G′的 Euler 闭迹。因此 )(\ CEG′ 必有一个连通分支至少含有一条边。记这个连通分支为
0
G 。由于 C 是闭迹，故
0
G 中没有奇度顶点，
且 )()(
0
GG ′<εε 。 由 G′的选择可知，
0
G 必有 Euler 闭迹
0
C 。 由于 G′连通,故 C 必经过
0
G
中至少一个顶点，从而 φ≠)()(
0
CVCV ∩ 。因此
0
CC + 是 G′ 的一条闭迹，且
)()(
0
CCC εε >+,这与 C 的选取矛盾。证毕。
充分性的另一种证法（数学归纳法）,
无妨设 1)( >Gν 。因 G 连通且无奇度顶点，故 2)( ≥Gδ,因而必含有圈。
当 2)( =Gν 时，设仅有的两点为 u,v，则 u,v 间必有偶数条边，它们显然构成 Euler 回路。
假设 kG =)(ν 时，结论成立。
当 1)( += kGν 时，任取 )(GVv∈ 。令 S = {v 的所有关联边 }。记 S 中的边为
m
eee null,,
21
，其中 )(vdm = 为偶数。记 vGG \=′ 。对 G′作如下操作,
（ 1） 任取 See
ji
∈,，设 vve
ii
=,vve
jj
= ；
（ 2）
ji
vvGG +′=′:,},{\:
ji
eeSS = ；
（ 3） 若 φ=S,则令 vGG?′=′:,停止；否则转（ 1）继续。
这个过程最终得到的 G′有 k 个顶点，且每个顶点在 G′中的度与在 G 中完全一样。由归纳假设,G′中有 Euler 闭迹，设为 P。将 P 中上述添加边
ji
vv 都用对应的两条边
ji
ee,代替，
显然获得 G 的一条 Euler 闭迹。证毕。
定理 4.1.2 一个连通图有 Euler 迹当且仅当它最多有两个奇度顶点。
证明 必要性,设连通图 G 有 Euler 迹 T，其起点和终点分别为 u,v。
若 )(GEuv∈,则 G 有 Euler 闭迹，由定理 4.1.1,G 无奇度顶点。
若 Guv?,则 uvG + 有 Euler 闭迹。由定理 4.1.1，图 uvG + 无奇度顶点。故 G 最多只可能有两个奇度顶点。
充分性,若 G 无奇度顶点，则由定理 4.1.1,G 有 Euler 闭迹，自然有 Euler 迹。
若 G 只有两个奇度顶点，设其为 u,v，则给 G 添加一条新边 uve = 所得的图 G +e 的每个顶点都是偶度顶点。从而 G +e 有 Euler 闭迹。故 G 有 Euler 迹。证毕。
一个图 G 如果有一条欧拉迹或欧拉闭迹，则我们可以沿着欧拉迹或欧拉闭迹连续而不重复地把 G 的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图，或者说它可一笔画成。如果图 G 可分解为两条迹或闭迹的并，则 G 的边可用两笔不重复地画完。同样地，如果图 G 可分解为 k 条迹或闭迹的并，则 G 可 k 笔画成。
3
定理 4.1.1 和定理 4.1.2 表明，一个图 G 可一笔画成的充分必要条件是 G 至多有 2 个奇度顶点。一般地，有下述推论。
推论 4.1.1 一个连通图可 k 笔画成当且仅当它最多有 2k 个奇度顶点。
证明留作习题。
Toida 于 1973 年发现，在一个欧拉图中，对任何一条边，经过它的圈的个数都是奇数。
1984 年,Mckee 又证明这个条件是充分的。这样便形成了对欧拉图的另一种刻画。
定理 4.1.3 一个非平凡连通图 G 是欧拉图的充分必要条件是 G 的每条边含在奇数个圈上。
证明：必要性：设 G 是欧拉图,则 G 的所有顶点都是偶数度的。任取 G 的一条边 e = uv,
因 G 有欧拉闭迹，故 GGe′=?是连通图。令 M 表示 G′中所有使顶点 u 恰好出现一次的不同的 u?v 迹组成的集合，这里两条迹相同是指两条迹的边数相同且每一步使用的边相同，
因此两条迹不同要么至少其中一条迹上有另一条迹所没有的边,要么两条迹使用边的次序不同。我们先来证明 M 含有奇数条迹。
从顶点 v 出发有奇数条边可作为迹的始边。一旦始边被确定，则这条迹就要继续到下一个顶点 w。由 于 除 vw 外 w 关联的边有奇数条，所以迹的第二条边有奇数种选择。如此继续，
直至到达迹的另一个端点 u。这表明始边使用 vw 的 u?v 迹有奇数条。对每一条始边都是如此，因此不同的 u?v 迹有奇数条。这里需要说明的是，如果迹中途重复经过某个顶点，上述递推过程仍然成立。
假设 T 是 G′中一条包含 u 恰好一次的 u?v 迹，但不是一条 u?v 路，则 T 必定重复经过了某些顶点，如果重复经过了顶点 v
1
，意味着 T 包含一条 v
1
v
1
闭迹 C，此时将 C“逆向”
使用,T 上其它边不变，便得到另一条 u?v 迹，我们称其为与 T 同类的 u?v 迹。可见，如果一条 u?v 迹重复经过 k 个点（多次经过的同一点的计重复经过次数）,则经这种逆向变换可获得 2
k
个同类 u?v 迹。这种分类构成一个等价关系，因此形成了对有重复点的 u?v 迹集合的划分。 划分出的每一个等价类有偶数个条 u?v 路。 这说明有重复点的 u?v 迹总共有偶数条。
有以上两方面知,GGe′=?中共有奇数条顶点不重复的 u?v 迹（即 u?v 路）,因此，
G 中共有奇数个含有边 e 的圈。
充分性：设 G 的每条边含在奇数个圈上，希望证明 G 的每个顶点都是偶数度的。任取顶点 v,设 v 关联的边共有 k 条，分别为
12
,,,
k
ee enull 。与这些边相应，构造一个有重边的图 H 如下,顶点集
12
H{,,,}
k
uu u= null,对于每个
i
u,相应于每个既含有
i
e 也含有某个
j
e 的圈，在
i
u 和
j
u 之间连一条边。
由于
i
e 含在奇数个圈上，且每个经过
i
e 的圈必经过
12
,,,
k
ee enull 中某条其它边，因此 H
中顶点
i
u 的度为奇数。 由
i
u 的任意性,H 中每个点的都是奇数。 由公式
1
2(H) ( )
k
i
i
duε
=
=
∑
知，
H 的顶点个数 k 必须是偶数，从而可知在 G 中顶点 v 关联偶数条边。由 v 的任意性,G 中所有点都是偶数度顶点，故为欧拉图。证毕。
4
三、求 Euler 图中的 Euler 闭迹－ Fleury 算法
对于复杂一些的图，即使判定出它有欧拉闭迹，也未必能很快地找出一条欧拉闭迹。在许多大规模应用中，需要借助于算法来找欧拉闭迹。 Fleury 给出了一个在欧拉图中找欧拉闭迹的多项式时间算法
[1]
。其基本思想是，从图中一个顶点出发，用深度优先方法找图的迹，
在任何一步，尽可能不使用剩余图的割边，除非没有别的选择。
[1] E,Lucas,Récréations Mathématiques IV,Paris,1921,
Fleury 算法的步骤如下,
输入：欧拉图 G
输出,G 的欧拉闭迹。
step1,任取 )(
0
GVv ∈,令
00
,vw =,0:=i 。
step2,设迹
iii
vevevw null
110
= 已取定。从 },,,{\
21 i
eeeE null 中选取一条边
1+i
e,使得
（ 1）
1+i
e 和
i
v 相关联；
（ 2）
1+i
e 不选 },,,{\
21 ii
eeeGG null= 的割边，除非没有别的选择。
step3,当 step2 不能再执行时，停止。
定理 4.1.3 若 G 是 Euler 图，则 Fleury 算法终止时得到的是 G 的 Euler 闭迹。
证明 设 G 是 Euler 图，
nnn
veevevW null
2110
= 是 Fleury 算法终止时得到的迹。则显然
n
v 在
},,,{\
21 nn
eeeGG null= 中的度数是 0（ 因算法终止在
n
v,若不是 0，则算法应继续 ） 。故
n
vv =
0
（ 否则
n
v 在 G 中是奇度顶点，这不可能 ）,即
n
W 是闭迹。
若
n
W 不是 G 的 Euler 闭迹，设 S = {
n
G 中度 >0 的所有顶点 }。则 φ≠S （因
n
W 不是 G
的 Euler 闭迹，有边不在
n
W 上）,且
n
W 上有 S 中的点（ 否则
n
G 中
n
W 上的点都是
n
G 的孤立点,这与 G 是 Euler 图 （从而连通） 矛盾 ）,但 SGVSv
n
\)(=∈ 。 设 m 是
n
W 上使得 Sv
m
∈
而 Sv
m
∈
+1
的最大整数。因
n
W 终止于 SGVS \)(=,故
11 ++
=
mmm
vve 是
m
G 中 ],[ SS 的仅有的一条边，因而是
m
G 的一条割边。
设 e 是
m
G 中和
m
v 关联的另一条边（ 因 0)( >
mG
vd
n
，这样的边 e 一定存在 ）,则由算法第二步知,e 必定也是
m
G 的一条割边 （ 否则,按算法应选 e 而不选
1+m
e ）,因而 e 是 ][SG
m
的割边。
S S
v
0
= v
n
v
m
e e
m+1
v
m+1
5
但由于
n
W 是闭迹,Svv
n
∈=
0
，且对 Sv∈?,)(vd
G
是偶数。故 ][SG
m
= []
n
GS中每个顶点都是偶数度顶点，由此又推出 ][SG
m
无割边（第二章习题 11） 。
以上两方面矛盾。证毕。
Fleury 算法的计算复杂度分析留给读者。
§ 2.中国邮递员问题（ Chinese Postman Problem）
中国邮递员问题（管梅谷,1960）,一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。请为他选择一条路线，使其所行路程尽可能短。
图论模型,求赋权连通图中含所有边的权最小的闭途径。这样的闭途径称为 最优回路 。
算法思想,（ 1）若 G 是 Euler 图，则 G 的 Euler 闭迹便是最优回路，可用 Fleury 算法求得；
（ 2）若 G 不是 Euler 图，则含有所有边的闭途径必须重复经过一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边的权相等）,最终消除了奇度顶点形成一个 Euler 图。因此，在这种情况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到 Euler 图
*
G,使得添加边的权之和
∑
∈Fe
ew )( 最小,（其中 )(\)(
*
GEGEF = ） ；然后用 Fleury 算法求
*
G 的一条 Euler
闭迹。这样便得到 G 的最优回路。
问题是：如何给图 G 添加重复边得到 Euler 图
*
G,使得添加边的权之和
∑
∈Fe
ew )( 最小？
方法 一（图上作业法）
定理 4.2.1 设 C 是一条经过赋权连通图 G 的每条边至少一次的回路，则 C 是 G 的最优回路当且仅当 C 对应的欧拉图
*
G 满足,
（ 1） G 的每条边在
*
G 中至多重复出现一次；
（ 2） G 的每个圈上在
*
G 中重复出现的边的权之和不超过该圈总权的一半。
证明 必要性：先证（ 1）
设 C 是最优回路，即 C 是它所对应的
*
G 的一个 Euler 闭迹。假设 G 中的边 uve = 被 C
经过了 m 次，即在
*
G 中 u,v 之间有 m 条重边。若 3≥m,则在
*
G 中删去这 m 条边中的两条，不改变 u,v 的度数的奇偶性。所得图 G′仍为 Euler 图，但 )()(
*
GwGw <′,即 G′中的欧拉闭迹是比 C 更优的一条投递路线，这是矛盾的。
下证（ 2） 。
设
1
C 是 G 中一个圈，且在
*
G 中，
1
C 上重复出现的边的权之和 >
1
C 的权的一半。将
1
C
上重复的边改为不重复而未重复的边改为重复边。
6
这样做不改变
*
G 中
1
C 上各顶点的度数的奇偶性。设所得图为 G
~
，则 G
~
仍是欧拉图，但
)()
~
( GwGw <,G
~
的欧拉闭迹比 C 更优。这是不可能的。
充分性,设
1
C 是 G 的一条投递路线 （经过每条边至少一次的回路）,它对应的欧拉图
*
1
G
满足（ 1）和（ 2） 。设
2
C 是 G 的一个最优回路，我们来证明
12
() ()wC wC= 。
设
*
2
G 是
2
C 对应的欧拉图（由必要性知，
*
2
G 满足（ 1）和 (2)）,
1
F,
2
F 分别为
*
1
G 和
*
2
G
的重复边集合。令 )(\)(
2121
FFFFF ∩∪=,而 [F]为 F 在
*
2
*
1
GG ∪ 中的导出子图（ [F]
中的边全是
1
F 和
2
F 的边，且无一边既在
1
F 中又在
2
F 中） 。
由于在
*
1
G 和
*
2
G 中，给一个顶点 v 添加边的条数的奇偶性与度数 )(vd
G
的奇偶性相同，
故 [F]中各顶点的度数均为偶数。这表明 [F]各连通分支均为欧拉图。从而 [F]是若干个圈的边不重的并。而且 [F]中各圈均既有
1
F 的边又有
2
F 的边（因
1
F 的边不会形成圈，
2
F 的也是） 。
由条件（ 2）,[F]中任一个圈 C′上
1
F 的边的权之和与
2
F 的边的权之和均不超过 )(
2
1
Cw ′ 。
于是
1
F,
2
F 在 C′上边的权之和必都等于 )(
2
1
Cw ′ 。这说明 [F]中属于
1
F 的边的权之和＝ [F]
中属于
2
F 的边的权之和。因此 )()(
*
1
*
2
GwGw =,从而 )()(
12
CwCw = 。
证毕。
奇偶点图上作业法,
先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。
奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，
计算量很大，实际当中用得较少。
方法二（ Edmonds-Johnson 方法）
定理 4.2.2 设 G 是赋权连通图,G 中有 k2 个奇度顶点。设
,|{ EeeA ∈= 在求最优回路时 e 被添加重复边 }。
则 G[A]是以 G 的奇度顶点为起点和终点的 k 条无公共边的最短路之并。
该定理的证明较长，有兴趣的读者可参看文献 [2]。
F
2
F
1
E(G
2
*
)
E(G
1
*
)
E(G)
7
基于此定理,Edmonds 和 Johnson 于 1973 年给出了求解邮递员问题的一个有效算法
[2]
。
Edmonds-Johnson 算法,
Step1,若 G 中无奇度顶点，令 GG =
*
，转 step2；否则转 step3。
Step2,求 G
*
中的 Euler 回路，结束。
Step3,求 G 中所有奇度顶点对之间的最短路。
Step4,以 G 中奇度顶点集 V′ 为顶点集，构作赋权完全图 |)|(,VnK
n
′=,使得对
Vvv
ji
′∈?,，
n
K 中边
ji
vv 的权为
i
v 至
j
v 在 G 中最短路的权。
Step5,求
n
K 中最小权完美匹配 M。
Step6,将 M 中边对应的各最短路中的边在 G 中加重复边，得 Euler 图 G
*
，转 step2。
注,该算法的复杂度为 )(
2
νO 。
例 4.2.1 求下图 G 的最优投递路线,A 为邮局。
解,G 只有两个奇点,},{ EBV =′ 。 B 到 E 的最短路为 BAFE，权为 13。完全赋权图
2
K 及相应的 Euler 图 G
*
为
易求得其 Euler 闭迹，并得到最优回路。
有关欧拉图和中国邮递员问题的更多内容可参看文献
[2] J,Edmonds and E.L,Johnson,Matching,Euler tours and the Chinese postman,Mathematical
Programming,5(1973) 88-124,
[3] H,Fleischner,Eulerian graphs,in Selected Topics in Graph Theory II (L,W,Beineke,and R.J,
Wilson eds.),Academic Press,London,(1983) 17-54,
[4] N,Christofides,Graph Theory-An Algorithmic Approach,Academic Press,Inc.,New York,
1990,
[5] G,Chartrand,and O.R,Oellermann,Applied and Algorithmic Graph Theory,McGraw-Hill,
Inc.,New York,1993,
[6] 谢政，网络算法与复杂性理论（第二版）,国防科技大学出版社,2003 年。
[7]H,Hamers,P,Borm,R Van de Leensel,and S,Tijs,Cost allocation in the Chinese postman
problem,Eur,J,Oper,Res.,118(1999) 153-163,
[8] D,Granot,H,Hamers,On the equivalence between some local and global Chinese postman
and traveling salesman graphs,Discrete Applied Mathematics,134(2004),67-76,
A
F
E
D
CB
4
3
10
14
8
5
6
5
9
E B
13
A
F
E
D
CB
4
3
10
14
8
5
6
5
9
G
*
K
2
8
§ 4.3Hamilton 图
定义 4.3.1 经过图 G 的每个顶点恰一次的路称为 G 的 Hamilton 路,简称为 H 路。经过图 G
的每个顶点恰一次的圈称为 G 的 Hamilton 圈,简称为 H 圈。具有 Hamilton 圈的图称为
Hamilton 图,简称为 H 图。
Hamilton 图的研究起源于一种十二面体上的游戏。 1857 年，爱尔兰著名数学家 William
Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体,在正十二面体的每个顶点上有一个木栓,并标有世界著名城市的名字。
游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。这个游戏当时称为 Icosian 游戏，也称为周游世界游戏。
将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。
周游世界游戏用图论术语来说就是判断十二面体图是否 Hamilton 图,并设法找出其 Hamilton
圈。其中一条 Hamilton 圈如图中粗边所示。
十二面体图是 H 图
判断一个图是否 Hamilton 图与判断一个图是否 Euler 图似乎很相似,然而二者却有本质的不同。目前为止尚没有找到判别一个图是否是 Hamilton 图的有效充要条件。这是图论和计算机科学中未解决的重要难题之一。
本节给出一些经典的充分条件和必要条件。
一、必要条件
定理 4.3.1 设 G 是二部图，若 G 是 H 图，则 G 必有偶数个顶点。
证明：设 G = (X,Y ),由于 G 的边全在 X 和 Y 之间，因此如果 G 有 Hamilton 圈 C，则 G
的所有顶点全在 C 上,且必定是 X 的点和 Y 的点交替在 C 上出现,因此 G 必有偶数个顶点。
证毕。
这个定理给出了一个二部图不是 Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是 Hamilton 图。例如，下列 Herschel 图是二部图，但有奇数个顶点，
故不是 H 图。
Herschel 图不是 H 图
9
定理 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 可判断下面 (1)中的图不是 H 图。事实上，令 S={u,v,w}，则
W(G－ S) = 4 > | S |。
但无法用该定理给出的必要条件来判断 (2)中的 Petersen 图不是 H 图。
二、充分条件
（ 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 null
21
。
这里 uv =
1
,vv =
ν
，令
}|{
1
EuvvS
ii
∈=
+
和 }|{ EvvvT
ii
∈= 。
由于 TSv ∪?
ν
，故 ν<|| TS ∪,并且 0|| =TS ∩ （因为若 TSv
i
∩∈?,则 G 将包含 H
圈
11121
vvvvvvv
ii +?
nullnull
νν
，矛盾） 。
故 ν<+=+=+ ||||||||)()( TSTSTSvdud ∩∪,这与
2
ν
δ ≥ 的前提矛盾。证毕。
u
v w
（ 1）
（ 2）
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
10
(2) 闭包型条件
Ore 注意到，上述 Dirac 定理的证明过程中，条件
2
ν
δ ≥ 仅仅用来证明对不相邻顶点
u,v，有 ν≥+ )()( vdud 成立。因此可以将图存在 Hamilton 圈的条件由
2
ν
δ ≥ 弱化为
ν≥+ )()( vdud 。这样便得到下述定理。
定理 4.3.4（ Ore,1960）
[1]
设 G 是简单图,u 和 v 是 G 中不相邻的顶点,且 ν≥+ )()( vdud,
则 G 是 Hamilton 图当且仅当 G＋ uv 是 Hamilton 图。
证明：必要性是显然的。
充分性：若 G＋ uv 是 Hamilton 图而 G 不是，则与定理 4.3.3 一样可推出矛盾。证毕。
Bondy 和 Chvátal 用更一般的形式表述了 Ore 观察到的实质，得到了图存在长度为 k
的圈和其它子图的充分条件 ( k υ= 时便是 Hamilton 圈 )
[2]
。他们用到了闭包的概念。
定义,图 G 的 闭包 （ closure） 是指由如下方法所得之图：反复连接 G 中度之和不小于 ν 的不相邻顶点对，直到没有这样的顶点对为止。图 G 的闭包通常记为 C(G)。
例如，对下列两图，前一个图的闭包是它自己，后一个图的闭包是完全图 K
5
。
定理 4.3.5 G 的闭包 C(G)是唯一确定的。
证明：设
21
,GG 是按闭包构成方法从 G 所得的两个闭包。用
m
eee,,,
21
null 和
n
fff,,,
21
null 分别表示在构作
21
,GG 过程中给 G 添加边的序列。我们用反证法来证明每个
i
e 一定是
2
G 的边，且每个
j
f 一定是
1
G 的边。
假设
m
eee,,,
21
null 中有不属于
2
G 的边，取序列中第一条不属于
2
G 的边设为 uve
k
=,
令
},,,{
121?
+=
k
eeeGH null 。
由
1
G 的定义知,ν≥+ )()( vdud
HH
。但 H 也是
2
G 的子图，因此由 ν≥+ )()( vdud
HH
知
ν≥+ )()(
22
vdud
GG
。而由
k
e 的选择,u,v 在
2
G 中是不相邻的，这与
2
G 是闭包矛盾。故每条
i
e 都必是
2
G 的边。
同理可证，每条
j
f 一定是
1
G 的边。这说明图 G 的闭包是唯一的。证毕。
定理 4.3.6（ Bondy & Chvátal,1976）
[2]
一个简单图是 Hamilton 图当且仅当它的闭包是
Hamilton 图。
证明：在构作闭包过程中，反复运用定理 4.3.4 即可。证毕。
11
根据该定理，下一个结论是显然的。
推论 4.3.1 设 G 是 3≥ν 的简单图。若 C(G)是完全图，则 G 是 Hamilton 图。
定理 4.3.2 后的例子改动一条边后所得的如下图，可以检验它的闭包是完全图，因而是
Hamilton 图。
（ 3）度序列条件
Chvátal 发现，如果图 G 满足：若有某些顶点的度比较小，则就有相应另一些顶点的度足够大,那么 G 就会成为 Hamilton 图。 具体来说,设简单图 G 的顶点度为
12
dd d
υ
≤≤≤null,
如果对任意正整数
2
m
υ
<,要么
m
dm>,要么
m
dm
υ
υ
≥?，则 G 是 Hamilton 图。这个结论正式叙述如下。
定理 4.3.7 (Chvátal,1972)
[3]
设 G 至少含有 3 个顶点的简单图，其度序列为 (
12
,,,dd d
υ
null )，
这里
12
dd d
υ
≤≤≤null 。若不存在小于
2
υ
的 m 使得 md
m
≤ 和
m
dm
υ
υ
<? 同时成立，则
G 是 Hamilton 图。
证明：设 G 满足定理条件。我们来证明 G 的闭包 C(G)是完全图。用反证法。
假设 C(G)不是完全图。设 u,v 是 C(G)中两个不相邻顶点，满足 )()( vdud ≤,且
)()( vdud + 尽可能大。 （ )(vd 表示 v 在 C(G)中的度） 。由 C(G)的定义,() ()du dv υ+<。
令
wuVwuN |}{\{)( ∈= 在 C(G)中与 u 不相邻 };
wvVwvN |}{\{)( ∈= 在 C(G)中与 v 不相邻 };
则 |()| 1 ()Nu duυ=,|()| 1 ()Nv dvυ= 。记 mud =)(,则 |()| 1Nu mυ=,
|()| 1 () 1( () 1Nv dv du mυυυ= > =? (1)
另外，由 u,v 的选择（ )()( vdud + 尽可能大）知,}{)( uuN ∪ 中每个顶点在 C(G)中的度不超过 )(vd （否则，设 )(uNv ∈′,)()( vdvd >′,则 )()( vdud ′+ > )()( vdud +,当初应当选择 u 和 v′） 。同理,N (v)中每个顶点在 C(G)中的度不超过 )(ud 。结合（ 1）式可知,
C(G)中至少有 m?ν 个顶点，其度 mvd?<≤ ν)(,（比如 }{)( uuN ∪ 中的顶点） ；
C(G)中至少有 m 个顶点，其度 m≤,（比如 )(vN 中的顶点） ；
12
由于 G 是 C(G)的子图，故上述结论对 G 也成立。按照度序列的排列方式，便有 md
m
≤ 和
md
m
<
ν
ν
，并且
2
ν
<m （因 )()( vdud ≤ 及 ν<+ )()( vdud ） 。这与定理的条件矛盾。
该矛盾说明 C(G)确实是完全图。由推论 4.3.1,G 是 Hamilton 图。证毕。
关于 Hamilton 图的更多结果可参看 [4],[5]
[1] O.Ore,Noye on Hamilton circuits,Amer,Math,Monthly,67(1960),55,
[2] J.A,Bondy,and V,Chvátal,A method in graph theory,Discrete Mathematics,15(1976),
111-136
[3] V,Chvátal,On Hamilton’s ideals,J,Combinatorial Theory (B),12(1972),163-168,
[4] V,Chvátal,Hamiltonian cycles,in The Traveling Salesman Problem,A Guided Tour of
Combinatorial Optimization (ed,E.L,Lawler,J.K,Lenstra,A.H.G,Rinnooy Kan,D.B,Shmoys),
Wiley,(1985),403-429,
[5] J.-C,Bermond,Hamiltonian graph,in Selected Topics in Graph Theory (L,W,Beineke,and
R.J,Wilson eds.),Academic Press,London,(1978) 127-168
§ 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 圈的近似算法。
13
近似算法 1－邻近点法
step1,任选一点 Vv ∈
1
，令 1:,
11
== ivP 。
Step2,设已得到
ii
vvvP null
21
=,选取 },,{\
211 ii
vvvVv null∈
+
使得权 )(
1+ii
vvw 最小。
Step3,若 ni =,则停止，
1211
vvvvvvPC
nnn
null=+= 是一条近似的最小 Hamilton 圈；否则 1,+= ii,转 step2。
例 4.4.1 求如下赋权完全图的最小权的 Hamilton 圈。
解：因 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 圈的权。
证明较长，从略。
近似算法 2－最小生成树法
step1,求
n
K 的一棵最小生成树 T；
step2,将 T 中各边均添加一条重边，设所得图为
*
G ；
step3,求
*
G 的从某点 v 出发的一条 Euler 闭迹
v
E ；
step4,按如下方法求出 G 的一条 Hamilton 路：从顶点 v 出发，沿 E
v
访问 G
*
中各顶点。在此过程中，一旦遇到重复顶点，就跳过它直接走到 Euler 环游上的下一个顶点。直到访问完所有顶点为止。
例 4.4.2 用最小生成树法求如下赋权完全图的最小权 Hamilton 圈。
解,求解过程图示如下。先求出一棵最小生成树 T,T 的各边加重边后得 G
*
,G
*
从 a 点出
5
5
5
8
8
9
9
7 16
12
a
b
c d
e
14
发的一条 Euler 闭迹为 C = aeadabcba，从 a 点出发沿 C 依次访问各点，遇到已访问过的点时直接跳到 C 的下一个点，这样便得到近似的最小权 Hamilton 圈 aedcba。
注,（ 1）若由不止一棵最小生成树，则最小生成树的选择会影响最终的结果 (H 圈的权 )。
（ 2） Euler 闭迹路线也影响最终结果。
（ 3）选择 Euler 闭迹的不同起点也影响最终的结果。
定理 4.4.2 设赋权完全图的各边之权均为正数，且对 Vvvv
kji
∈?,,，都有
()( ) ()
ij jk ik
wvv wvv wvv+≥，则 2
*
0
<
c
c
。这里
0
c 是算法 2 所得的 Hamilton 圈 H 的权（近似最优值）,而
*
c 是最小 Hamilton 圈
*
H 的权。
证明：设 T 和 G
*
如算法所述。设 E 是 G
*
中一条 Euler 闭迹。由于对 Vvvv
kji
∈?,,，都有
)()()(
kikjji
vvwvvwvvw ≥+,故 )(2)()(
0
TwEwcHw =≤= 。此外，设 T′是 G 的最小
Hamilton 圈
*
H 删去任一边后所得的生成树，则
*
)()( cTwTw <′≤ 。因而
*
0
2cc < 。证毕。
近似算法 3－最小权匹配法 (Christofides 算法 )
[ 1]
step1,求完全图
n
K 的一棵最小生成树 T
step2,设 T 中奇度顶点的集合为 },,,{
221 k
vvvV null=′ 。求 V′的导出子图
k
KVG
2
][ =′ 的最小权完美匹配，将得到的 k 条边添加到 T 上，得 Euler 图 G
*
。
step3,求出 G
*
的从某顶点 v 出发的一条 Euler 闭迹
v
E 。
step4,从 v 出发沿
v
E 访问 G
*
的各个顶点。在此过程中，一旦遇到重复顶点，就跳过它直接走到 Euler 闭迹上的下一个顶点。直到访问完所有顶点为止。
[1] N,Christofides,Worst-case analysis of a new heuristic for the traveling salesman problem,
Technical Report,Graduate School of Industrial Administration,Carnegie-Mellon University,
Pittsburgh,PA(1976),
例 4.4.3 用 Christofides 法求如下赋权完全图的最小权 Hamilton 圈。
解,求解过程图示如下。先求出一棵最小生成树 T，再求出 T 中奇度顶点集合 V′={a,c,d,e}
在 G 中导出的子图 []GV′,并求出 []GV′ 的最小权完美匹配 {ae,cd}。将这两条匹配边添加到 T 上，得 Euler 图 G
*
。 G
*
从 a 点出发的一条 Euler 闭迹为 C = aeadcba，从 a 点出发沿 C
依次访问各点，遇到已访问过的点时直接跳到 C 的下一个点，这样便得到近似的最小权
Hamilton 圈 aedcba。
G
最小生成树 T 加重边后得 G
*
近似最优 H 圈
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
5
5
8
9
a
b
c d
e
9
15
G 最小生成树 T ][VG ′ G
*
定理 4.4.3 设赋权完全图的各边之权均为正数，且对 Vvvv
kji
∈?,,，都有
)()()(
kikjji
vvwvvwvvw ≥+,
则
2
3
*
0
<
c
c
。 这里
0
c 是算法 3 所得的 Hamilton 圈 H 的权 (近似最优值 )，而
*
c 是 G 的最小
Hamilton 圈
*
H 的权。
证明：先证四条事实,
（ 1）
*
H 去掉一条边后便得一生成树，故
*
)( cTw < 。
（ 2）由于对 Vvvv
kji
∈?,,，都有 )()()(
kikjji
vvwvvwvvw ≥+,故 )(
0 v
Ewc ≤ 。
（ 3）设
k
KVG
2
][ =′ 中最小权 Hamilton 圈的权为 c′。因 ][VG ′ 是完全图
n
K 的子图,][VG ′
的 Hamilton 圈可由
n
K 的 Hamilton 圈通过“去二添一”手续得到，故
*
cc ≤′ 。
（ 4）因 ][VG ′ 中最小 Hamilton 圈上交替取边可得 ][VG ′ 的一个完美匹配，故 ][VG ′ 中最小权完美匹配 M 中各边权之和
2
)(
c
Mw
′
≤ 。
由以上四条，得
*
*
*
0
2
3
2
)()()( c
c
cMwTwEwc
v
=+<+=≤ 。证毕。
TSP 问题是一个内容十分丰富而又非常活跃的研究方向。有关 TSP 问题的进一步了解可参看 [7]~[9]，有关 TSP 问题算法的新进展可参看 [10]~[18]
[7] E.L,Lawler,J.K,Lenstrar,A.H.G,Rinnooy and D.B,Shmoys,The Traveling Salesman
Problem,New York,Wiley-Interscience,1986,
[8] N,Christofides,Graph Theory-An Algorithmic Approach,Academic Press,Inc.,New York,
1990,
[9] G,Chartrand,and O.R,Oellermann,Applied and Algorithmic Graph Theory,McGraw-Hill,
Inc.,New York,1993,
[10] S,Arora,Polynomial time approximation schemes for Euclidean TSP and other geometric
problems,Proceedings of 37
th
Annual Sym,Foundation of Computer Science,Oct,1996,
[11] S,Arora,Nearly linear time approximation schemes for Euclidean TSP and other geometric
problems,Proceedings of 38
th
Annual Sym,Foundation of Computer Science,Oct,1997,
[12] D,Applegate,R,Bixby,On the Solution of traveling salesman problems,Documenta
Mathematica J,DMV,Extra Volume ICM 1998 III,(1998) 645-656,
[13] C.S.Mata and J.Mitchell,Approximation algorithms for Geometric tour and network
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
16
problems,in Proceeding of 11
th
ACM Symposium on Computing Geomrtry,1995,360-369,
[14] G,Reinelt,TSPLIB-A traveling salesman problem library,ORSA J,Computing,3(1991)
376-384,
[15] J,Bentley,Fast algorithms for geometric traveling salesman problem,ORSA J,on Computing,
4(1992) 387-411,
[16] E,Lawler,J.K,Lenstra,A,Rinnooy Kan,D,Shmoys(eds.),The Traveling Salesman Problem,
Wiley,UK,1989,
[17] J.Potters,I,Curiel,S,Tijs,Traveling salesman games,Math,Programming,53(1992)
199-211,
[18] D,Granot,H,Hamers,On the equivalence between some local and global Chinese postman
and traveling salesman graphs,Discrete Applied Mathematics,134(2004),67-76,
第四章习题
1,证明：一个连通图可 k 笔画完当且仅当它最多有 2k 个奇度顶点。
2,若 G 是 Euler 图，则 G 的每个块也是 Euler 图。
3,确定 m 和 n 的值是的完全二部图
,
K
mn
是欧拉图。
4,证明或否定,（ 1）每个欧拉二部图有偶数条边； （ 2）含偶数个顶点的每个欧拉简单图哟偶数条边。
5,是否存在偶数个顶点、奇数条边的欧拉图？若不存在，给出理由；若存在，举出例子。
6,图 G 是欧拉图的充分必要条件是 G 可表成无公共边的圈的并。
7,下列两图是否分别可以一笔画？若可以，找出画法；若不可以，说明理由。
8,判断 Herschel 图和 Petersen 图分别能几笔画成。
9,给出一个算法，用以在有欧拉迹的图中求一条欧拉迹。
10,判断下图 1 是否 Euler 图。若是，用 Fleury 算法求其一个 Euler 环游。
G
1
G
1
Herschel 图 Petersen 图
17
11,求图 2 的一条最优邮路。
12,多米诺骨牌每一块上有 0,1,2,3,4,5,6 七个数字之一（ 0 用 O 表示，其它数字用点数表示） 。将标有不同数字的多米诺骨牌组成骨牌对子，如 (0,1),(2,4)等（无序对）,
共可组成
76
21
2
×
= 个不同的对子。现要将这 21 个对子首尾相接连起来，使得对任何两个相邻的对子，前一个对子的尾数与后一个对子的首数相等，问是否能按此规则将之 21
个骨牌对子连成一个圆圈？
13,用丝线将 mn× 个珍珠穿成一个网（如图）,现在想将一些丝线段剪断，得到一个由这些珍珠做成的项链，问 m 和 n 应满足什么条件？
14,判断下列图形是否 Hamilton 图，若是，找出一条 Hamilton 圈；若不是，说明理由。
15,设 G 是二部图 G=(X,Y)。若 |X|≠ |Y|,则 G 不是 Hamilton 图。
16,证明 Petersen 图不是 Hamilton 图（图见题 7） 。
17,给出一种方法，将完全二部图 K
n,n
分解为
2
n
个两两无公共边的 Hamilton 圈的并。
18,证明：若 G 不是 2－连通图，则 G 不是 Hamilton 图。
19,设 2k ≥,证明顶点数为 2k?1 的 k 次正则图是 Hamilton 图。
20,若图 G 的任二顶点间有 Hamilton 路，则称 G 是 Hamilton 连通图。证明,G 是 Hamilton
连通图且 (G) 4υ ≥,则
31
(G)
2
υ
ε
+
> 。
21,若 G 有 Hamilton 路，则对 V(G)的每个真子集 S，有 W(G – S)≦ |S|+1。
图 1 图 2
9
68
4
3
F
9
5
7
E
DB
C
A
18
22,证明：简单图 G 有 Hamilton 路当且仅当 G + K
1
有 Hamilton 圈。
23,设简单图 G 的度序列为
12
dd d
υ
≤≤≤null 。证明：若对任意正整数
1
2
m
υ +
<,要么
m
dm>,要么
1m
dm
υ
υ
+
≥?，则 G 有 Hamilton 路。
24,设 G 是一个简单图,(G) 3υ ≥,如果对满足 1
2
m
υ
≤ ≤ 的任意正整数 m，度不超过 m
的顶点个数比 m 小，则 G 是 Hamilton 图。
25,教室里有 6 排椅子，每排 5 张椅子，每张椅子坐一名学生。现在班主任老师考虑每周调整一次学生们的座位，使得每个学生都调到本次调整前与他相邻的某个座位上（前后左右视为相邻）,一个学期内每个学生都不能调回到他已经坐过的座位上。请帮老师制定一个调整方案。如果老师现在改变了主意，希望每次将每个学生调到原先与他不相邻的某个座位上，问是否可行？应怎样调整？
26,若围一张圆桌坐着至少 6 个人，那么一定可以调整他们的位置，使得每个人两侧都挨着新邻居。
27,某楼层的平面结构示意图如下。试说明从前门进去经过每个门口恰好一次且从后门出去是不可能的。
28,一个博物馆称为设计良好的，如果存在经过每个房间恰好一次的参观路线。某博物馆的楼层平面设计如下图，试证明这个博物馆的设计不是良好的。
后门前门
