中国邮递员问题小论文.doc

中国邮递员问题
摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。本文主要介绍了中国邮递员问题的基本分析、求解中国邮递员问题的方法以及有关欧拉回路的算法实现。
关键词：中国邮递员 欧拉图 欧拉回路 Fleury算法
一、 中国邮递员问题的分析
中国邮递员问题是我国数学家管梅谷先生在20世纪60年代提出来的。该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？用图论的语言来描述就是在一个带权图G中，能否找到一条回路C，使C包含G的每条边至少一次且C的长度最短？如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少一遍，这时用中国邮路问题算法可求出最短路径。
此问题求解的关键点分析：
(1)若G没有奇度数结点，则G是欧拉图，于是欧拉回路C是惟一的最小长度的投递路线。
(2)若G恰有两个奇度数结点Vi和Vj，则G具有欧拉迹，且邮局位于结点Vi，则邮递员走遍所有的街道一次到达结点Vj；从Vj返回Vi可选择其间的一条最短路径。这样，最短邮路问题转化为求Vi到 Vj的欧拉迹和Vj到Vi的最短路径问题。
(3)若 G 中奇数度结点的数目多于2，则回路中必须增加更多的重复边( 路径)。这时，怎样使重复边的总长度最小？
二、三种情况的具体思路
1、若G没有奇度数结点，则G是欧拉图，则欧拉回路是唯一的最小长度投递路线。此时可以利用求欧拉回路的Fleury算法求解。步骤为：
任意选取一个顶点V0、使W0=V0。
‚假设迹Wi=V0e1V1```eiVi已经确定，那么按照下述方面从E/{e1,e2,```ei}中选取边ei+1。
a、 ei+1和Vi相关联
b、 除非没有别的边可选择，否则ei+1不是G=G-{e1,e2,```ei}的割边c。
ƒ当‚不能再继续时，停止。
2、 若G恰有两个奇度数结点
若G只有两个奇点Vi,Vj则有从Vi到Vj的欧拉迹，从Vj回到Vi则必须重复一些边，使重复边的总长度最小，转化为求从Vi到Vj的最短路径。算法如下：
 找出奇点Vi,Vj之间的最短路径P；
‚ 令G， = G + P；
ƒG，为欧拉图，G，的欧拉回路即为最优邮路。
3、 G 中奇数度结点的数目多于2
求解中国邮递员问题的传统方法是通过计算奇度数结点之间的最短路径来确定结点配对，添加重复边。但是，从上面定理的结论可以看出，当图中的奇度数结点数目较多时，其计算量将非常大。因此，我们可以考虑，既然核心问题是要解决奇度数结点的配对问题并在奇度数结点之间添加重复边，那么不妨将原始图中的偶度数结点去掉，只考虑奇度数结点，并利用最小生成树的观点来快速地找出奇度数结点的最优配对方案。具体思路如下：
去掉原始图中的偶度数结点，即得到的新图中只包含原奇度数结点与它们之间的路径；
‚求新图的最小生成树；
ƒ由最小生成树确定奇度数结点的配对；
④在原始图中添加重复边。
例 求解如图1 所示的中国邮递员问题。
解 如图 1 所示，该中国邮递员
问题共有 8 个奇度数结点，即 V2，V4，V5，V6，V7，V8，V10，V12。

图1
‚去掉图 1 中的偶度数结点，得到新图 2。

图2
ƒ求图 2 的最小生成树(如图 3 所示)。

图3
④由图 3 可知 V2与 V6配对，V4与 V8配对，V5与 V1 2配对，V7与 V10配对。
⑤根据奇度数结点的配对在原始图1中添加重复边(如图 4 所示)，经检验此方案已是最优。

图4
这种方法为求解多奇数度点的情况提供了一种很完整又相对简便的解法。采用先去掉偶度点的办法，可以将次要条件剔除，更为直观简便地研究问题，穿过现象看本质。奇数点的最小生成树的研究可以知道树是具有最小权的连通生成子图。在一棵树里，任两点均由唯一的路连接，所以找到的是最优树。
参考文献
[1] 舒兴明. 利用 Floyed-Hungary 法求解中国邮路问题.华南热带农业大学学报.
[2] Herbert Fleischner.欧拉图与相关专题.科学出版社.
[3]李盘林.离散数学（第二版）.高等教育出版社.