中科院研究生院专业基础课：《图论与网络流理论》第四章 Euler图和Hamilton图（高随祥）.pdf_大学文库

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 闭迹。对∀v ∈V(G)，v 必在 C 上出现。因 C 每经过 v 一次，就有两条与 v 关联的边被使用。设 C 经过 v 共 k 次，则d(v) = 2k 。充分性：无妨设ν (G) > 1。因 G 连通，故至少有一条边。下面用反证法证明充分性结论。假设图 G 无奇度顶点，但它不是 Euler 图。令 S={G|G 至少有一条边，无奇度顶点，且不是 Euler 图}

则S≠φ。取S中边数最少的一个,记为G′。因(G’)≥2,故G”含有圈,因而含有闭迹。设C是G′中一条最长的闭迹。由假设,C不是G′的 Euler闭迹。因此G"\E(C)必有一个连通分支至少含有一条边。记这个连通分支为G0。由于C是闭迹,故G中没有奇度顶点, 且E(G0)E(C),这与C的选取矛盾。证毕充分性的另一种证法(数学归纳法) 无妨设v(G)>1。因G连通且无奇度顶点,故δ(G)≥2,因而必含有圈。当v(G)=2时,设仅有的两点为uv,则u间必有偶数条边,它们显然构成 Euler回路假设v(G)=k时,结论成立。当v(G)=k+1时,任取v∈V(G)。令S={ν的所有关联边}。记S中的边为 e1,e2,…en,其中m=d(v)为偶数。记G′=G\。对G作如下操作: (1)任取e12e,∈S,设e1=v",e (2)G′=G+vy,S=SVe,e (3)若S=φ,则令G′=G-ν,停止:否则转(1)继续。这个过程最终得到的G’有k个顶点,且每个顶点在G′中的度与在G中完全一样。由归纳假设,G中有 Euler闭迹,设为P。将P中上述添加边vv都用对应的两条边e,e,代替显然获得G的一条 Euler闭迹。证毕。定理412一个连通图有 Euler迹当且仅当它最多有两个奇度顶点证明必要性:设连通图G有 Euler迹T,其起点和终点分别为l,va 若∈E(G),则G有 Euler闭迹,由定理4..1,G无奇度顶点。若lgG,则G+有 Euler闭迹。由定理41.1,图G+l无奇度顶点。故G最多只可能有两个奇度顶点充分性:若G无奇度顶点,则由定理41.1,G有 Euler闭迹,自然有 Euler迹。若G只有两个奇度顶点,设其为u,则给G添加一条新边e=u所得的图G+e的每个顶点都是偶度顶点。从而G+e有 Euler闭迹。故G有 Euler迹。证毕。个图G如果有一条欧拉迹或欧拉闭迹,则我们可以沿着欧拉迹或欧拉闭迹连续而不重复地把G的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图,或者说它可一笔画成。如果图G可分解为两条迹或闭迹的并,则G的边可用两笔不重复地画完。同样地,如果图G可分解为k条迹或闭迹的并,则G可k笔画成

2 则 S ≠ φ 。取 S 中边数最少的一个，记为G′。因δ (G′) ≥ 2 ，故G′含有圈，因而含有闭迹。设 C 是G′中一条最长的闭迹。由假设，C 不是G′的 Euler 闭迹。因此G′ \ E(C) 必有一个连通分支至少含有一条边。记这个连通分支为G0 。由于 C 是闭迹，故G0 中没有奇度顶点，且 ( ) ( ) ε G0 ε C ，这与 C 的选取矛盾。证毕。充分性的另一种证法（数学归纳法）：无妨设ν (G) > 1。因 G 连通且无奇度顶点，故δ (G) ≥ 2 ，因而必含有圈。当ν (G) = 2 时，设仅有的两点为 u,v，则 u,v 间必有偶数条边，它们显然构成 Euler 回路。假设ν (G) = k 时，结论成立。当ν (G) = k +1 时，任取 v ∈V (G) 。令 S = {v 的所有关联边}。记 S 中的边为 m e , e ,"e 1 2 ，其中m = d(v) 为偶数。记G′ = G \ v 。对G′作如下操作：（1）任取ei , e j ∈ S ，设e v v i = i ，e v v j = j ；（2） i j G′ := G′ + v v ， : \ { , } i j S = S e e ；（3）若 S = φ ，则令G′ := G′ − v ，停止；否则转（1）继续。这个过程最终得到的G′有 k 个顶点，且每个顶点在G′中的度与在 G 中完全一样。由归纳假设，G′中有 Euler 闭迹，设为 P。将 P 中上述添加边 i j v v 都用对应的两条边 i j e , e 代替，显然获得 G 的一条 Euler 闭迹。证毕。定理 4.1.2 一个连通图有 Euler 迹当且仅当它最多有两个奇度顶点。证明必要性：设连通图 G 有 Euler 迹 T，其起点和终点分别为 u, v。若uv ∈ E(G) ，则 G 有 Euler 闭迹，由定理 4.1.1，G 无奇度顶点。若uv ∉G ，则G + uv 有 Euler 闭迹。由定理 4.1.1，图G + uv 无奇度顶点。故 G 最多只可能有两个奇度顶点。充分性：若 G 无奇度顶点，则由定理 4.1.1，G 有 Euler 闭迹，自然有 Euler 迹。若 G 只有两个奇度顶点，设其为 u,v，则给 G 添加一条新边e = uv 所得的图 G +e 的每个顶点都是偶度顶点。从而 G +e 有 Euler 闭迹。故 G 有 Euler 迹。证毕。一个图 G 如果有一条欧拉迹或欧拉闭迹，则我们可以沿着欧拉迹或欧拉闭迹连续而不重复地把 G 的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图，或者说它可一笔画成。如果图 G 可分解为两条迹或闭迹的并，则 G 的边可用两笔不重复地画完。同样地，如果图 G 可分解为 k 条迹或闭迹的并，则 G 可 k 笔画成

定理41.1和定理412表明,一个图G可一笔画成的充分必要条件是G至多有2个奇度顶点。一般地,有下述推论推论411一个连通图可k笔画成当且仅当它最多有2k个奇度顶点。证明留作习题 Noida于1973年发现,在一个欧拉图中,对任何一条边,经过它的圈的个数都是奇数 1984年, Mckee又证明这个条件是充分的。这样便形成了对欧拉图的另一种刻画定理413一个非平凡连通图G是欧拉图的充分必要条件是G的每条边含在奇数个圈上证明:必要性:设G是欧拉图,则G的所有顶点都是偶数度的。任取G的一条边e=l, 因G有欧拉闭迹,故G′=G-e是连通图。令M表示G’中所有使顶点u恰好出现一次的不同的uv迹组成的集合,这里两条迹相同是指两条迹的边数相同且每一步使用的边相同因此两条迹不同要么至少其中一条迹上有另一条迹所没有的边,要么两条迹使用边的次序不同。我们先来证明M含有奇数条迹从顶点ν出发有奇数条边可作为迹的始边。一旦始边被确定,则这条迹就要继续到下个顶点w。由于除w外w关联的边有奇数条,所以迹的第二条边有奇数种选择。如此继续直至到达迹的另一个端点u。这表明始边使用w的y迹有奇数条。对每一条始边都是如此,因此不同的uv迹有奇数条。这里需要说明的是,如果迹中途重复经过某个顶点,上述递推过程仍然成立假设T是G′中一条包含u恰好一次的u-v迹,但不是一条uv路,则T必定重复经过了某些顶点,如果重复经过了顶点η,意味着T包含一条v1-V1闭迹C,此时将C“逆向” 使用,T上其它边不变,便得到另一条u-y迹,我们称其为与T同类的u迹。可见,如果条u迹重复经过k个点(多次经过的同一点的计重复经过次数),则经这种逆向变换可获得2k个同类uy迹。这种分类构成一个等价关系,因此形成了对有重复点的v迹集合的划分。划分出的每一个等价类有偶数个条uv路。这说明有重复点的u-v迹总共有偶数条。有以上两方面知,G’=G-e中共有奇数条顶点不重复的v迹(即vv路),因此, G中共有奇数个含有边e的圈充分性:设G的每条边含在奇数个圈上,希望证明G的每个顶点都是偶数度的。任取顶点v,设v关联的边共有k条,分别为e1,e2,…,ek。与这些边相应,构造一个有重边的图H如下:顶点集H={4,2…,4},对于每个l,相应于每个既含有e也含有某个e的圈,在u,和u2之间连一条边由于e含在奇数个圈上,且每个经过e的圈必经过e,e2,…,e4中某条其它边,因此H 中顶点L1的度为奇数由的任意性H中每个点的都是奇数由公式2E(H)=∑d(u)知, H的顶点个数k必须是偶数,从而可知在G中顶点v关联偶数条边。由v的任意性,G中所有点都是偶数度顶点,故为欧拉图。证毕

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 有欧拉闭迹，故G G ′ = − e 是连通图。令 M 表示G′中所有使顶点 u 恰好出现一次的不同的 u−v 迹组成的集合，这里两条迹相同是指两条迹的边数相同且每一步使用的边相同，因此两条迹不同要么至少其中一条迹上有另一条迹所没有的边，要么两条迹使用边的次序不同。我们先来证明 M 含有奇数条迹。从顶点 v 出发有奇数条边可作为迹的始边。一旦始边被确定，则这条迹就要继续到下一个顶点 w。由于除 vw 外 w 关联的边有奇数条，所以迹的第二条边有奇数种选择。如此继续，直至到达迹的另一个端点 u。这表明始边使用 vw 的 u−v 迹有奇数条。对每一条始边都是如此，因此不同的 u−v 迹有奇数条。这里需要说明的是，如果迹中途重复经过某个顶点，上述递推过程仍然成立。假设 T 是G′中一条包含 u 恰好一次的 u−v 迹，但不是一条 u−v 路，则 T 必定重复经过了某些顶点，如果重复经过了顶点 v1，意味着 T 包含一条 v1 −v1 闭迹 C，此时将 C“逆向” 使用，T 上其它边不变，便得到另一条 u−v 迹，我们称其为与 T 同类的 u−v 迹。可见，如果一条 u−v 迹重复经过 k 个点（多次经过的同一点的计重复经过次数），则经这种逆向变换可获得2k 个同类 u−v 迹。这种分类构成一个等价关系，因此形成了对有重复点的 u−v 迹集合的划分。划分出的每一个等价类有偶数个条 u−v 路。这说明有重复点的 u−v 迹总共有偶数条。有以上两方面知，G G ′ = − e 中共有奇数条顶点不重复的 u−v 迹（即 u−v 路），因此， G 中共有奇数个含有边 e 的圈。充分性：设 G 的每条边含在奇数个圈上，希望证明 G 的每个顶点都是偶数度的。任取顶点 v，设 v 关联的边共有 k 条，分别为 1 2 ,, , k ee e " 。与这些边相应，构造一个有重边的图 H 如下：顶点集 H {, , , } 1 2 k = uu u " ，对于每个 i u ，相应于每个既含有 i e 也含有某个 j e 的圈，在 i u 和 j u 之间连一条边。由于 i e 含在奇数个圈上，且每个经过 i e 的圈必经过 1 2 ,, , k ee e " 中某条其它边，因此 H 中顶点 i u 的度为奇数。由 i u 的任意性，H 中每个点的都是奇数。由公式 1 2 (H) ( ) k i i ε d u = = ∑ 知， 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. 任取 ( ) v0 ∈V G ，令 0 0 w := v ，i := 0 。 step2. 设迹 i i i w v e v "e v = 0 1 1 已取定。从 \ { , , , } 1 2 i E e e " e 中选取一条边 i+1 e ，使得（1） i+1 e 和 i v 相关联；（2） i+1 e 不选 \ { , , , } i 1 2 i G = G e e " e 的割边，除非没有别的选择。 step3. 当 step2 不能再执行时，停止。定理 4.1.3 若 G 是 Euler 图，则 Fleury 算法终止时得到的是 G 的 Euler 闭迹。证明设 G 是 Euler 图， n n n W v e v e "e v = 0 1 1 2 是 Fleury 算法终止时得到的迹。则显然 n v 在 \ { , , , } n 1 2 n G = G e e " e 中的度数是 0（因算法终止在 n v ，若不是 0，则算法应继续）。故 n v = v 0 （否则 n v 在 G 中是奇度顶点，这不可能），即Wn 是闭迹。若Wn 不是 G 的 Euler 闭迹，设 S = {Gn 中度>0 的所有顶点}。则 S ≠ φ （因Wn 不是 G 的 Euler 闭迹，有边不在Wn 上），且Wn 上有 S 中的点（否则Gn 中Wn 上的点都是Gn 的孤立点，这与 G 是 Euler 图（从而连通）矛盾），但vn ∈ S = V (G) \ S 。设 m 是Wn 上使得 vm ∈ S 而vm+1 ∈ S 的最大整数。因Wn 终止于 S =V (G) \ S ，故 m+1 = m m+1 e v v 是Gm 中[S, S ] 的仅有的一条边，因而是Gm 的一条割边。设 e 是Gm 中和 mv 关联的另一条边（因dG (vm ) > 0 n ，这样的边 e 一定存在），则由算法第二步知：e 必定也是Gm 的一条割边（否则，按算法应选 e 而不选 m+1 e ），因而 e 是G [S] m 的割边。 S S v0 = vn vm e em+1 vm+1

但由于Wn是闭迹,V0=V∈S,且对vv∈S,d(v)是偶数。故Gn[S]=G[S]中每个顶点都是偶数度顶点,由此又推出Gn[S]无割边(第二章习题11)l 以上两方面矛盾。证毕 Fleury算法的计算复杂度分析留给读者。 §2中国邮递员问题( Chinese Postman Problen) 中国邮递员问题(管梅谷,1960):一位邮递员从邮局出发投递邮件,经过他所管辖的每条街道至少一次,然后回到邮局。请为他选择一条路线,使其所行路程尽可能短图论模型:求赋权连通图中含所有边的权最小的闭途径。这样的闭途径称为最优回路。算法思想:(1)若G是 Euler图,则G的 Euler闭迹便是最优回路,可用 Fleury算法求得; (2)若G不是Euer图,则含有所有边的闭途径必须重复经过一些边,最优回路要求重复经过的边的权之和达到最小。闭途径重复经过一些边,实质上可看成给图G添加了一些重复边(其权与原边的权相等),最终消除了奇度顶点形成一个 Euler图。因此,在这种情况下求最优回路可分为两步进行:首先给图G添加一些重复边得到 Euler图G,使得添加边的权之和∑w(e)最小,(其中F=E(G)\E(G));然后用 Fleury算法求G的一条 Euler 闭迹。这样便得到G的最优回路。问题是:如何给图G添加重复边得到Eder图G,使得添加边的权之和∑we)最小? 方法一(图上作业法) 定理421设C是一条经过赋权连通图G的每条边至少一次的回路,则C是G的最优回路当且仅当C对应的欧拉图G满足 (1)G的每条边在G中至多重复出现一次 (2)G的每个圈上在G中重复出现的边的权之和不超过该圈总权的一半。证明必要性:先证(1) 设C是最优回路,即C是它所对应的G的一个 Euler闭迹。假设G中的边e=l被C 经过了m次,即在G中uv之间有m条重边。若m≥3,则在G中删去这m条边中的两条,不改变uv的度数的奇偶性。所得图G仍为 Euler图,但w(G)C1的权的一半。将C1 上重复的边改为不重复而未重复的边改为重复边

5 但由于Wn 是闭迹， v0 = vn ∈ S ，且对∀v ∈ S ， d (v) G 是偶数。故G [S] m = [ ] G S n 中每个顶点都是偶数度顶点，由此又推出G [S] m 无割边（第二章习题 11）。以上两方面矛盾。证毕。 Fleury 算法的计算复杂度分析留给读者。 §2.中国邮递员问题（Chinese Postman Problem）中国邮递员问题（管梅谷，1960）：一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。请为他选择一条路线，使其所行路程尽可能短。图论模型：求赋权连通图中含所有边的权最小的闭途径。这样的闭途径称为最优回路。算法思想：（1）若 G 是 Euler 图，则 G 的 Euler 闭迹便是最优回路，可用 Fleury 算法求得；（2）若 G 不是 Euler 图，则含有所有边的闭途径必须重复经过一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边的权相等），最终消除了奇度顶点形成一个 Euler 图。因此，在这种情况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到 Euler 图 * G ，使得添加边的权之和 ∑e∈F w(e)最小，（其中 ( ) \ ( ) * F = E G E G ）；然后用 Fleury 算法求 * G 的一条 Euler 闭迹。这样便得到 G 的最优回路。问题是：如何给图 G 添加重复边得到 Euler 图 * G ，使得添加边的权之和∑e∈F w(e)最小？方法一（图上作业法）定理 4.2.1 设 C 是一条经过赋权连通图 G 的每条边至少一次的回路，则 C 是 G 的最优回路当且仅当 C 对应的欧拉图 * G 满足：（1） G 的每条边在 * G 中至多重复出现一次；（2） G 的每个圈上在 * G 中重复出现的边的权之和不超过该圈总权的一半。证明必要性：先证（1）设 C 是最优回路，即 C 是它所对应的 * G 的一个 Euler 闭迹。假设 G 中的边e = uv 被 C 经过了 m 次，即在 * G 中 u,v 之间有 m 条重边。若m ≥ 3 ，则在 * G 中删去这 m 条边中的两条，不改变 u,v 的度数的奇偶性。所得图G′仍为 Euler 图，但 ( ) ( ) * w G′ C1的权的一半。将C1 上重复的边改为不重复而未重复的边改为重复边

6 这样做不改变 * G 中C1上各顶点的度数的奇偶性。设所得图为G ~ ，则 G ~ 仍是欧拉图，但 ) ( ) ~ w(G < w G ，G ~ 的欧拉闭迹比 C 更优。这是不可能的。充分性：设C1是 G 的一条投递路线（经过每条边至少一次的回路），它对应的欧拉图 * G1 满足（1）和（2）。设C2 是 G 的一个最优回路，我们来证明 1 2 wC wC () () = 。设 * G2 是C2 对应的欧拉图（由必要性知， * G2 满足（1）和(2)），F1、F2 分别为 * G1 和 * G2 的重复边集合。令 ( ) \ ( ) F = F1 ∪ F2 F1 ∩ F2 ，而[F]为 F 在 * 2 * G1 ∪ G 中的导出子图（ [F] 中的边全是 F1和 F2 的边，且无一边既在 F1中又在 F2 中）。由于在 * G1 和 * G2 中，给一个顶点 v 添加边的条数的奇偶性与度数d (v) G 的奇偶性相同，故[F]中各顶点的度数均为偶数。这表明[F]各连通分支均为欧拉图。从而[F]是若干个圈的边不重的并。而且[F]中各圈均既有 F1的边又有 F2 的边（因 F1的边不会形成圈， F2 的也是）。由条件（2），[F]中任一个圈C′上 F1的边的权之和与 F2 的边的权之和均不超过 ( ) 2 1 w C′ 。于是 F1、F2 在C′上边的权之和必都等于 ( ) 2 1 w C′ 。这说明[F]中属于 F1的边的权之和＝[F] 中属于 F2 的边的权之和。因此 ( ) ( ) * 1 * w G2 = w G ，从而 ( ) ( ) w C2 = w C1 。证毕。奇偶点图上作业法：先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，计算量很大，实际当中用得较少。方法二（Edmonds-Johnson 方法）定理 4.2.2 设 G 是赋权连通图，G 中有2k 个奇度顶点。设 A = {e | e ∈ E,在求最优回路时 e 被添加重复边}。则 G[A]是以 G 的奇度顶点为起点和终点的 k 条无公共边的最短路之并。该定理的证明较长，有兴趣的读者可参看文献[2]。 F1 F2 E(G2 * E(G ) 1 * ) E(G)

7 基于此定理，Edmonds 和 Johnson 于 1973 年给出了求解邮递员问题的一个有效算法[2]。 Edmonds-Johnson 算法： Step1. 若 G 中无奇度顶点，令G = G * ，转 step2；否则转 step3。 Step2. 求 G* 中的 Euler 回路，结束。 Step3. 求 G 中所有奇度顶点对之间的最短路。 Step4. 以 G 中奇度顶点集 V ′ 为顶点集，构作赋权完全图 K , (n |V |) n = ′ ，使得对 ∀vi , v j ∈V ′， Kn 中边 i j v v 的权为 i v 至 j v 在 G 中最短路的权。 Step5. 求 Kn 中最小权完美匹配 M。 Step6. 将 M 中边对应的各最短路中的边在 G 中加重复边，得 Euler 图 G* ，转 step2。注：该算法的复杂度为 ( ) 2 O ν 。例 4.2.1 求下图 G 的最优投递路线，A 为邮局。解：G 只有两个奇点，V ′ = {B, E}。B 到 E 的最短路为 BAFE，权为 13。完全赋权图 K2 及相应的 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 B C 4 3 10 14 8 5 6 5 9 B E 13 A F E D B C 4 3 10 14 8 5 6 5 9 G* K2

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 图

10 (2) 闭包型条件 Ore 注意到，上述 Dirac 定理的证明过程中，条件 2 ν δ ≥ 仅仅用来证明对不相邻顶点 u,v，有 d(u) + d(v) ≥ν 成立。因此可以将图存在 Hamilton 圈的条件由 2 ν δ ≥ 弱化为 d(u) + d(v) ≥ν 。这样便得到下述定理。定理 4.3.4（Ore，1960）[1] 设 G 是简单图，u 和 v 是 G 中不相邻的顶点，且d(u) + d(v) ≥ν ，则 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)。例如，对下列两图，前一个图的闭包是它自己，后一个图的闭包是完全图 K5。定理 4.3.5 G 的闭包 C(G)是唯一确定的。证明：设 1 2 G ,G 是按闭包构成方法从 G 所得的两个闭包。用 m e , e , , e 1 2 " 和 n f , f , , f 1 2 " 分别表示在构作 1 2 G ,G 过程中给 G 添加边的序列。我们用反证法来证明每个 i e 一定是G2 的边，且每个 j f 一定是G1 的边。假设 m e , e , , e 1 2 " 中有不属于G2 的边，取序列中第一条不属于G2 的边设为 e uv k = ，令 { , , , } = + 1 2 k−1 H G e e " e 。由G1 的定义知，d H (u) + d H (v) ≥ν 。但 H 也是G2 的子图，因此由d H (u) + d H (v) ≥ν 知 ( ) + ( ) ≥ν 2 2 d u d v G G 。而由 k e 的选择，u、v 在G2 中是不相邻的，这与G2 是闭包矛盾。故每条 i e 都必是G2 的边。同理可证，每条 j f 一定是G1 的边。这说明图 G 的闭包是唯一的。证毕。定理 4.3.6（Bondy & Chvátal,1976）[2] 一个简单图是 Hamilton 图当且仅当它的闭包是 Hamilton 图。证明：在构作闭包过程中，反复运用定理 4.3.4 即可。证毕