Euler图中的中国邮路问题的Fleury算法

【摘要】本文首先对什么是中国邮路问题以及它的图论模型进行了解释，并对只含有偶顶点的Euler图中的中国邮路问题用Fleury算法做了解答，而这一方法在解决含有奇顶点的一般性的中国邮路问题，同样具有重要的参考价值。

【关键词】Euler图，中国邮路问题，Fleury算法（3）顶V的次数记成d(v)。若从顶引出的该图形的弧的条数为奇数，则称这个顶为奇顶点，顶的次数为奇次；若为偶数，则顶为偶顶点，顶的次数为偶次。

中国邮路问题及其图论模型

中国邮路问题也称中国邮递员问题，是我国数学家管梅谷于1960年首次提出来的，这个问题的实际模型是：一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过由他负责投递的每条街道至少一次，为这位邮递员设计一条投递线路，使其耗时最少。我们上述的问题用图图形的语言表示出来，就有中国邮路问题的图论模型： Euler图中的中国邮路问题

4.1 Euler图的相关概念

定义1 :图中含有每一条边的行迹叫做Euler行迹；闭的Euler行迹叫做Euler回路；含有Euler回路的图叫做Euler图。直观地讲，欧拉图就是从一个顶点出发每条边恰好通过一次又能回到出发顶点的那种图，即不重复的行遍所有的边再回到出发点。下面给出Euler图的特征性描述：

4.2Fleury算法求解Euler回路中的中国邮路问题

一般的，在图中都有奇次顶点存在，如若不然，则图中的所有顶点都是偶次点，即d(v)是偶数，这满足我们上面的命题（2），由三个命题间的等价关系，我们可以推出这样的图为Euler图。如果G是Euler图，则所求的中国邮路W就是一条Euler回路。值得注意的是，即使已知G是Euler图，如果没有一定的路线遵循，也不是漫不经心就可以找出它的一个Euler回路的。如下面的图1是一个Euler图，设从V1开始，要找到一条Euler回路，如果开始三步是V1V3V2V1就找不出了,因为回到V1之后发现左边K5的上的边没有用过，而V1得关联边已经全部用过，不能从V1再回到左边那些没有用过的边了.这样走失败的原因，是因为用了V1V3边之后，在未用过的边们导出的子图上V2V3是桥，提前过桥V3V2的结果就是断了去左边K5的后路。这里我们得到一个教训就是，不是必要的时候，不要通过未用过的边的导出子图的桥，根据这样的思路，就有求Euler图中中国邮路的Fleury算法。Fleury算法: