第四章 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(G)。由G′的选择可知,G必有 Euler闭迹Co。由于G′连通,故C必经过Go 中至少一个顶点,从而(C)∩F(C0)≠φ。因此C+C0是G’的一条闭迹,且 E(C+C0)>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 < ε G′ 。由G′的选择可知，G0 必有 Euler 闭迹C0 。由于G′连通，故 C 必经过G0 中至少一个顶点，从而 V (C) ∩V (C0 ) ≠ φ 。因此 C + C0 是 G′ 的一条闭迹，且 ( ) ( ) ε C + C0 > ε 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)<w(G),即G′中的 欧拉闭迹是比C更优的一条投递路线,这是矛盾的。 下证(2) 设C1是G中一个圈,且在G中,C1上重复出现的边的权之和>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′ < w G ，即G′中的 欧拉闭迹是比 C 更优的一条投递路线，这是矛盾的。 下证（2）。 设C1是 G 中一个圈，且在 * G 中，C1上重复出现的边的权之和>C1的权的一半。将C1 上重复的边改为不重复而未重复的边改为重复边