1
第四章 Euler图和Hamilton图
§ 1. Euler 图
一、基本概念
七桥问题： 如下图。从任一陆地点出发，经过每座桥一次且仅一次回到出发点，是否可能？
?
哥尼斯堡七桥 G
转化为 图论问题 ：图 G 中从任一顶点出发，经过每条边恰好一次回到出发点，是否可能？
Euler 环游 (tour,circuit,closed trail)：经过图 G 的每条边恰好一次的闭迹。
Euler 迹（ trail） ：经过每条边恰好一次的迹。
Euler 图：有 Euler 环游的图。
七桥问题：图 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 图 }
则 φ≠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 I 。因此
0
CC + 是 G′ 的一条闭迹，且
)()(
0
CCC εε >+ ，这与 C 的选取矛盾。证毕。
2
充分性的另一种证法（数学归纳法） ：
无妨设 1)( >Gν 。因 G 连通且无奇度顶点，故 2)( ≥Gδ ，因而必含有圈。
当 2)( =Gν 时，设仅有的两点为 u,v，则 u,v 间必有偶数条边，它们显然构成 Euler 回路。
假设 kG =)(ν 时，结论成立。
当 1)( += kGν 时，任取 )(GVv∈ 。令 S = {v 的所有关联边 }。记 S 中的边为
m
eee L,,
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 迹 C，其起点和终点分别为 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 迹。证毕。
推论 4.1.1 一个连通图可 k 笔画成当且仅当它最多有 2k 个奇度顶点。
证明留作习题。
例
三、求 Euler 图中的 Euler 环游－ Fleury 算法
step1. 任取 )(
0
GVv ∈ ，令
00
: vw = ， 0:=i 。
step2. 设迹
iii
vevevw L
110
= 已取定。从 },,,{21 i
eeeE L 中选取一条边
1+i
e ，使得
（ 1）
1+i
e 和
i
v 相关联；
3
（ 2）
1+i
e 不选 },,,{21 ii
eeeGG L= 的割边，除非没有别的选择。
step3. 当 step2 不能再执行时，停止。
定理 4.1.3 若 G 是 Euler 图，则 Fleury 算法终止时得到的是 G 的 Euler 环游。
证明 设 G 是 Euler 图，
nnn
veevevW L
2110
= 是 Fleury 算法终止时得到的迹。则显然
n
v 在
},,,{21 nn
eeeGG L= 中的度数是 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
的
割边。
但由于
n
W 是闭迹， Svv
n
∈=
0
，且对 Sv∈? ， )(vd
G
是偶数。故 ][SG
m
= ][SG
n
中
每个顶点都是偶数度顶点，由此又推出 ][SG
m
无割边（连通性一章习题） 。
以上两方面矛盾。证毕。
例 ：
S
S
v
0
= v
n
v
m
e e
m+1
v
m+1
1
5
4
32
6
4
§ 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
上重复的边改为不重复而未重复的边改为重复边。
5
这样做不改变
*
G 中
1
C 上各顶点的度数的奇偶性。设所得图为 G
~
，则 G
~
仍是欧拉图，但
)()
~
( GwGw < ， G
~
的欧拉环游比 C 更优。这是不可能的。
充分性：设
1
C 是 G 的一个最优回路，
*
1
G 是它对应的欧拉图；
2
C 是 G 的一条投递路线
（经过所有边的回路） ，它对应的欧拉图
*
2
G 满足（ 1）和（ 2） 。由必要性知，
*
1
G 也满足（ 1）
和（ 2） 。我们来证明 )()(
12
CwCw = 。
设
1
F 、
2
F 分别为
*
1
G 和
*
2
G 的重复边集合。令 )(\)(
2121
FFFFF IU= 。则 G[F]为 F
在
*
2
*
1
GG U 中的导出子图（ G[F]中的边全是
1
F 和
2
F 的边，且无一边既在
1
F 中又在
2
F 中） 。
由于在
*
1
G 和
*
2
G 中，过一个顶点 v 的添加边条数的奇偶性与度数 )(vd
G
的奇偶性相同，
故 G[F]中各顶点的度数均为偶数。这表明 G[F]各连通分支均为欧拉图。从而 G[F]是若干个
圈的边不重的并。而且 G[F]中各圈均既有
1
F 的边又有
2
F 的边（因
1
F 的边不会形成圈，
2
F
的也是） 。由条件（ 2） ， G[F]中任一个圈 C′上
1
F 的边的权之和与
2
F 的边的权之和均不超过
)(
2
1
Cw ′ 。于是
1
F 、
2
F 在 C′上边的权之和必都等于 )(
2
1
Cw ′ 。这说明 G[F]中属于
1
F 的边
的权之和＝ G[F]中属于
2
F 的边的权之和。因此 )()(
*
1
*
2
GwGw = ，从而 )()(
12
CwCw = 。
证毕。
奇偶点图上作业法：
先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。
奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，
计算量很大，实际当中用得较少。
方法二（ Edmonds-Johnson 方法）
定理 4.2.2 设 G 是赋权连通图， G 中有 k2 个奇度顶点。设
,|{ EeeA ∈= 在求最优回路时 e 被添加重复边 }。
则 G[A]是以 G 的奇度顶点为起点和终点的 k 条无公共边的最短路之并。
证明（略） 。
基于此定理， Edmonds 和 Johnson 于 1973 年给出了求解邮递员问题的有效算法。
Edmonds-Johnson 算法：
F
2
F
1
E(G
2
*
)
E(G
1
*
)
E(G)
6
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 。
例 ：求下图的最优投递路线， A 为邮局。
解：只有两个奇点， },{ EBV =′ 。 B 到 E 的最短路为 BAFE，权为 13。完全赋权图
2
K 及
相应的 Euler 图 G
*
为
K
2
G
*
易求得其 Euler 环游，并得到最优回路。
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
