这样做不改变G中C1上各顶点的度数的奇偶性。设所得图为G,则G仍是欧拉图,但 v(G)<w(G),G的欧拉闭迹比C更优。这是不可能的。 充分性:设C1是G的一条投递路线(经过每条边至少一次的回路),它对应的欧拉图G 满足(1)和(2)。设C2是G的一个最优回路,我们来证明w(C1)=v(C2) 设G2是C2对应的欧拉图(由必要性知,G2满足(1)和(2),F、F2分别为G1和G2 的重复边集合。令F=(F1∪F2)(F1∩F2),而鬥为F在G1UG2中的导出子图( 中的边全是F和F2的边,且无一边既在F中又在F2中)。 EFG2’) E 由于在G1和G2中,给一个顶点v添加边的条数的奇偶性与度数d(v)的奇偶性相同, 故[中各顶点的度数均为偶数。这表明[F各连通分支均为欧拉图。从而是若干个圈的边 不重的并。而且[F中各圈均既有F1的边又有F2的边(因F的边不会形成圈,F2的也是)。 由条件(2),[F中任一个圈C"上F1的边的权之和与F2的边的权之和均不超过w(C) 于是F1、F2在C上边的权之和必都等于w(C)。这说明中属于F1的边的权之和=[F 中属于F2的边的权之和。因此w(G2)=w(G1),从而w(C2)=w(C1)。 毕 奇偶点图上作业法 先分奇偶点,奇点对对联;联线不重迭,重迭要改变;圈上联线长,不得过半圈。 奇偶点图上作业法虽然通俗易懂,但使用时需要检查图的每个圈,对于有很多圈的图, 计算量很大,实际当中用得较少。 方法二( Edmonds- Johnson方法) 定理42.2设G是赋权连通图,G中有2k个奇度顶点。设 A={ele∈E,在求最优回路时e被添加重复边} 则O[4是以G的奇度顶点为起点和终点的k条无公共边的最短路之并 该定理的证明较长,有兴趣的读者可参看文献[2]
6 这样做不改变 * G 中C1上各顶点的度数的奇偶性。设所得图为G ~ ，则 G ~ 仍是欧拉图，但 ) ( ) ~ w(G < w G ，G ~ 的欧拉闭迹比 C 更优。这是不可能的。 充分性：设C1是 G 的一条投递路线（经过每条边至少一次的回路），它对应的欧拉图 * G1 满足（1）和（2）。设C2 是 G 的一个最优回路，我们来证明 1 2 wC wC () () = 。 设 * G2 是C2 对应的欧拉图（由必要性知， * G2 满足（1）和(2)），F1、F2 分别为 * G1 和 * G2 的重复边集合。令 ( ) \ ( ) F = F1 ∪ F2 F1 ∩ F2 ，而[F]为 F 在 * 2 * G1 ∪ G 中的导出子图（ [F] 中的边全是 F1和 F2 的边，且无一边既在 F1中又在 F2 中）。 由于在 * G1 和 * G2 中，给一个顶点 v 添加边的条数的奇偶性与度数d (v) G 的奇偶性相同， 故[F]中各顶点的度数均为偶数。这表明[F]各连通分支均为欧拉图。从而[F]是若干个圈的边 不重的并。而且[F]中各圈均既有 F1的边又有 F2 的边（因 F1的边不会形成圈， F2 的也是）。 由条件（2），[F]中任一个圈C′上 F1的边的权之和与 F2 的边的权之和均不超过 ( ) 2 1 w C′ 。 于是 F1、F2 在C′上边的权之和必都等于 ( ) 2 1 w C′ 。这说明[F]中属于 F1的边的权之和＝[F] 中属于 F2 的边的权之和。因此 ( ) ( ) * 1 * w G2 = w G ，从而 ( ) ( ) w C2 = w C1 。 证毕。 奇偶点图上作业法： 先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。 奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图， 计算量很大，实际当中用得较少。 方法二（Edmonds-Johnson 方法） 定理 4.2.2 设 G 是赋权连通图，G 中有2k 个奇度顶点。设 A = {e | e ∈ E,在求最优回路时 e 被添加重复边}。 则 G[A]是以 G 的奇度顶点为起点和终点的 k 条无公共边的最短路之并。 该定理的证明较长，有兴趣的读者可参看文献[2]。 F1 F2 E(G2 * E(G ) 1 * ) E(G)
基于此定理, 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 postman
7 基于此定理，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