Page 223 - 数学建模算法与应用
P. 223
第八章 图与网络模型及方法应用
二、Euler 回路的 Fleury 算法
1921 年，Fleury 给出下面的求 Euler 回路的算法。
Fleury 算法：
1.
2. 假设迹 i 已经选定，那么按下述方法从 中选取
边
1. 和 相关联；
2. 除非没有别的边可选择，否则 不是 的割边 (cut edge)。
( 所谓割边是一条删除后使连通图不再连通的边 )。
3°当第 2 步不能再执行时，算法停止。
三、 应用
（一）邮递员问题
中国邮递员问题
一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责
投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。
上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的
回路，且使此回路的权最小。
显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路。
对于非 Euler 图，1973 年，Edmonds 和 Johnson 给出下面的解法：
设 G 是连通赋权图。
1.
2. 对每对顶点 u，v ∈ V0 求 d(u，v)（d(u，v) 是 u 与 v 的距离，可用 Floyd
算法求得）。
3. 构造完全赋权图 K|V0 |，以 V0 为顶点集，以 d(u，v) 为边 uv 的权。
4. 求 中权之和最小的完美对集 M。
5. 求 M 中边的端点之间的在 G 中的最短轨。
6. 在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即
共端点共权的边）。
213
