、求 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