第四章 Euler图和 Hamilton图 S4.1 Euler图 基本概念 通常认为,图论见诸于文献的起始研究之一是瑞士数学家欧拉关于七桥问题的研究。在 世纪普鲁士的哥尼斯堡城( Konigsberg),普雷格尔( Pregel)河穿城流过,河中有两个河 心岛,有七座桥将小岛与河岸连接起来(如下图)。有市民尝试从河岸或岛屿的任一陆地点 出发,经过每座桥一次且仅一次回到出发点,但一直未能获得成功。人们怀疑,这样的走法 是否存在?这便是七桥问题。 哥尼斯堡七桥 1741年,欧拉经过对七桥问题的研究,发表了第一篇有关图论的论文,从而使七桥问 题闻名于世。欧拉将四块陆地用平面上四个点来表示,两块陆地间有一座桥相连,就在两个 相应的点间连一条边,最终获得如图1所示的一个图G。于是七桥问题转化为一个图论问题: 图G中从任一顶点出发,经过每条边恰好一次回到出发点,是否可能? 为了进一步的讨论,我们需要定义如下术语 Euler闭迹( closed trail,tour, circuit):经过图G的每条边恰好一次的闭迹 Euler迹(trai):经过每条边恰好一次的迹 Euler图:有 Euler闭迹的图 利用这些术语,七桥问题可叙述为:图1中的图G是否为 Euler图?欧拉对此做出了否 定的回答。事实上,欧拉研究了更一般的情况,获得了任意一个图是否为欧拉图的判定条件 、Euer图的判定 定理411一个非空连通图是Euer图当且仅当它没有奇度顶点。 证明必要性:设图G是 Euler图,C是G中一个 Euler闭迹。对vv∈V(G),v必在C上 出现。因C每经过v一次,就有两条与v关联的边被使用。设C经过v共k次,则d(v)=2k。 充分性:无妨设v(G)>1。因G连通,故至少有一条边。下面用反证法证明充分性结论。 假设图G无奇度顶点,但它不是 Euler图。令 G|G至少有一条边,无奇度顶点,且不是 Euler图}
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 中 所有点都是偶数度顶点，故为欧拉图。证毕
、求 Euler图中的 Euler闭迹一 Fleury算法 对于复杂一些的图,即使判定出它有欧拉闭迹,也未必能很快地找出一条欧拉闭迹。在 许多大规模应用中,需要借助于算法来找欧拉闭迹。 Fleury给出了一个在欧拉图中找欧拉闭 迹的多项式时间算法。其基本思想是,从图中一个顶点出发,用深度优先方法找图的迹 在任何一步,尽可能不使用剩余图的割边,除非没有别的选择。 [E. Lucas, Recreations Mathematiques IV, Paris, 192 Fleury算法的步骤如下 输入:欧拉图G 输出:G的欧拉闭迹 stepI.任取v∈V(G),令wo:=v,i:=0。 step2.设迹w1=vev1…ev已取定。从E\{e1,e2,…,e}中选取一条边e1,使得 (1)e1和v相关联 (2)en1不选G1=G\{e1,e2…e;}的割边,除非没有别的选择。 step3.当step2不能再执行时,停止。 定理413若G是 Euler图,则 Fleury算法终止时得到的是G的 Euler闭迹 证明设G是 Euler图,Wn=ve1ve2…enVn是 Fleury算法终止时得到的迹。则显然v在 Gn=G\{e12e2,…,en}中的度数是0(因算法终止在vn,若不是0,则算法应继续)。故 V=vn(否则vn在G中是奇度顶点,这不可能),即W是闭迹 若Wn不是G的 Euler闭迹,设S={Gn中度>0的所有顶点}。则S≠p(因Wn不是G 的 Euler闭迹,有边不在Wn上),且W上有S中的点(否则Gn中Wn上的点都是Gn的孤立 点,这与G是Euer图(从而连通)矛盾),但v∈S=(G)\S。设m是W上使得vn∈S 而vnm∈S的最大整数。因W终止于S=H(G)\S,故en=Vnvn+是Gn中[S,S]的仅 有的一条边,因而是Gn的一条割边。 设e是Gm中和vm关联的另一条边(因do(vn)>0,这样的边e一定存在),则由算 法第二步知:e必定也是Gn的一条割边(否则,按算法应选e而不选em),因而e是Gn[S] 的割边
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 上重复的边改为不重复而未重复的边改为重复边
这样做不改变G中C1上各顶点的度数的奇偶性。设所得图为G,则G仍是欧拉图,但 v(G)<w(G),G的欧拉闭迹比C更优。这是不可能的。 充分性:设C1是G的一条投递路线(经过每条边至少一次的回路),它对应的欧拉图G 满足(1)和(2)。设C2是G的一个最优回路,我们来证明w(C1)=v(C2) 设G2是C2对应的欧拉图(由必要性知,G2满足(1)和(2),F、F2分别为G1和G2 的重复边集合。令F=(F1∪F2)(F1∩F2),而鬥为F在G1UG2中的导出子图( 中的边全是F和F2的边,且无一边既在F中又在F2中)。 EFG2’) E 由于在G1和G2中,给一个顶点v添加边的条数的奇偶性与度数d(v)的奇偶性相同, 故[中各顶点的度数均为偶数。这表明[F各连通分支均为欧拉图。从而是若干个圈的边 不重的并。而且[F中各圈均既有F1的边又有F2的边(因F的边不会形成圈,F2的也是)。 由条件(2),[F中任一个圈C"上F1的边的权之和与F2的边的权之和均不超过w(C) 于是F1、F2在C上边的权之和必都等于w(C)。这说明中属于F1的边的权之和=[F 中属于F2的边的权之和。因此w(G2)=w(G1),从而w(C2)=w(C1)。 毕 奇偶点图上作业法 先分奇偶点,奇点对对联;联线不重迭,重迭要改变;圈上联线长,不得过半圈。 奇偶点图上作业法虽然通俗易懂,但使用时需要检查图的每个圈,对于有很多圈的图, 计算量很大,实际当中用得较少。 方法二( Edmonds- Johnson方法) 定理42.2设G是赋权连通图,G中有2k个奇度顶点。设 A={ele∈E,在求最优回路时e被添加重复边} 则O[4是以G的奇度顶点为起点和终点的k条无公共边的最短路之并 该定理的证明较长,有兴趣的读者可参看文献[2]
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)
基于此定理, Edmonds和 Johnson于1973年给出了求解邮递员问题的一个有效算法。 Edmonds-Johnson算法: Stepl.若G中无奇度顶点,令G=G,转step2;否则转step3。 Step2.求G中的 Euler回路,结束 Step3.求G中所有奇度顶点对之间的最短路 Step4.以G中奇度顶点集V为顶点集,构作赋权完全图Kn,(n=|VD,使得对 vv,v,∈,K,中边vy,的权为v至v在G中最短路的权 Step5.求Kn中最小权完美匹配M。 Step6.将M中边对应的各最短路中的边在G中加重复边,得 Euler图G,转step2 注:该算法的复杂度为O(v2)。 例42.1求下图G的最优投递路线,A为邮局。 A 1410>D 解:G只有两个奇点,={B,E}。B到E的最短路为BAFE,权为13。完全赋权图K2及 相应的Euer图G为 K 易求得其 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.J Wilson eds ) Academic Press, London, (1983)17-54 4 N. Christofides, Graph Theory-An Algorithmic Approach, Academic Press, Inc, New York 5]G Chartrand, and O.R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill 6]谢政,网络算法与复杂性理论(第二版),国防科技大学出版社,2003年。 [7H. Hamers, P Borm, R Van de Leensel, and S. Tijs, Cost allocation in the Chinese postman l18(1999)153-163 8] D. Granot, H Hamers, On the equivalence between some local and global Chinese postman
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
§43 Hamilton图 定义43.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图的有效充要条件。这是图论和 计算机科学中未解决的重要难题之 本节给出一些经典的充分条件和必要条件。 、必要条件 定理431设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图
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 图
定理43.2若G是H图,则对V(G)的每个非空真子集S,均有: 连通分支数W(G-S)≤|S|e 证明:设C是G的H圈,则对VG)的每个非空真子集S,均有 由于C-S是G-S的生成子图,故W(G-S)≤WC-S)≤|S 证毕 利用定理432可判断下面(1)中的图不是H图。事实上,令S={u,V,w},则 H(G-S)=4>|S| 但无法用该定理给出的必要条件来判断(2)中的 Petersen图不是H图。 (1) 、充分条件 (1)度型条件 定理433 Dirac,1952)若G是简单图,且v≥3,d≥一,则G是 Hamilton图 证明用反证法:假定定理不真。令 A={G|G的顶点数为v≥3,d≥,且G是非 Hamilton图}。 2 从A中取出边最多的一个,记为G。因v≥3,故不是完全图(否则G是 Hamilton图)。设 u和v是G的不相邻顶点。由G的选择,G+w是 Hamilton图。因G是非 Hamilton图,故 G+m的H圈必经过e=。于是G中存在以u为起点v为终点的 Hamilton路vv2…",。 这里v1=a,v=",令 S={v|a∈E}和T={v|vv∈E} Vi vi+l 由于 V E SUT,故S∪Tkv,并且S∩TF=0(因为若彐v,∈S∩T,则G将包含H 圈v1V2…vv,1…Vv1,矛盾)。 V1v2v3…vv+1…V1vr 故d(n)+d()=S|+|THSU7|+|S∩Tkv,这与d≥的前提矛盾。证毕
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 图。 证明 用反证法：假定定理不真。令 A = {G |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 路 ν v v "v 1 2 。 这里v = u 1 ，v = v ν ，令 { | } S = vi uvi+1 ∈ E 和T {v | v v E} = i i ∈ 。 由于vν ∉ S ∪T ，故| S ∪T |<ν ，并且| S ∩T |= 0 （因为若∃vi ∈ S ∩T ，则 G 将包含 H 圈 1 2 1 1 1 v v v v v v v " i ν ν − " i+ ，矛盾）。 故d(u) + d(v) =| S | + | T |=| S ∪T | + | S ∩T |<ν ，这与 2 ν δ ≥ 的前提矛盾。证毕。 u v w （1） （2） v1 v2 v3… vi vi+1… vv-1 vv u v v1 v2 v3… vi vj … vv-1 vv u v vi+1
(2)闭包型条件 Ore注意到,上述Diac定理的证明过程中,条件δ≥仅仅用来证明对不相邻顶点 l,,有d(a)+d(v)≥v成立。因此可以将图存在 Hamilton圈的条件由d≥弱化为 d(u)+d(v)≥v。这样便得到下述定理 定理434(Ore,1960)设G是简单图,和v是G中不相邻的顶点,且d(u)+d(v)≥v 则G是 Hamilton图当且仅当G+是 Hamilton图。 证明:必要性是显然的。 充分性:若G+w是 Hamilton图而G不是,则与定理433一样可推出矛盾。证毕。 Bondy和 Chvatal用更一般的形式表述了Ore观察到的实质,得到了图存在长度为k 的圈和其它子图的充分条件(k=D时便是 Hamilton圈/2。他们用到了闭包的概念。 定义:图G的闭包( closure)是指由如下方法所得之图:反复连接G中度之和不小于v的 不相邻顶点对,直到没有这样的顶点对为止。图G的闭包通常记为C(G) 例如,对下列两图,前一个图的闭包是它自己,后一个图的闭包是完全图K5 定理43.5G的闭包C(G)是唯一确定的。 证明:设G1G2是按闭包构成方法从G所得的两个闭包。用e1,e2…,em和f1,f2,…,fn分 别表示在构作G1,G2过程中给G添加边的序列。我们用反证法来证明每个e1一定是G2的 边,且每个∫,一定是G1的边 假设e,e2,…,em中有不属于G2的边,取序列中第一条不属于G2的边设为ek=l 令 H=G+{e,e2,…,ek-1} 由G1的定义知,dn(a)+dn(v)≥V。但H也是G2的子图,因此由dh(a)+dh(v)≥v知 da(u)+dn(v)≥v。而由ek的选择,、v在G2中是不相邻的,这与G2是闭包矛盾。故 每条e都必是G2的边。 同理可证,每条J/一定是G1的边。这说明图G的闭包是唯一的。证毕。 定理.3.6( Bondy& Chvatal,1976)一个简单图是 Hamilton图当且仅当它的闭包是 Hamilton 1图 证明:在构作闭包过程中,反复运用定理434即可。证毕
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 即可。证毕
