基于此定理, 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 postman7 基于此定理，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