问题及解答

Fleury 算法用于求欧拉图的欧拉巡回.

设 $G=(V,E)$ 是一无向欧拉图, 我们要求 $G$ 中一条欧拉巡回.

算法:

(1) 任取 $G$ 中一顶点 $v_0$, 令道路 $w_0=v_0$.

(2) 假定道路 $w_i=v_0 e_1 v_1 e_2\cdots e_i v_i$ 已经选好, 则从剩余的边集 $E_{i}^{c}:=E(G)-\{e_1,e_2,\ldots,e_i\}$ 中选择 $e_{i+1}$, 使得:

    (a) $e_{i+1}$ 与 $v_i$ 相关联;
    (b) 除非不能选择, 否则一定要使 $e_{i+1}$ 不是 $G_i:=G[E_i^c]$ 的割边(或桥 bridge).

(3) 当第(2)步不能再进行时算法停止.

可以证明当算法停止时, 所得到的道路 $w_m=v_0 e_1 v_1 e_2 v_2\ldots e_m v_m$ (这里 $v_m=v_0$) 是 $G$ 中的一个欧拉巡回(或欧拉回路).

References:

赵静、但琦 等编《数学建模与数学实验》（第四版）5.5.2 中国邮递员问题.  Page 104.

http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html