摘要:在一个图 G (V, E) 上，邮递员要走完每一个顶点，并且通过每条街道至少一次，即 每条边 e 上有非负权 w(e) ，还要能够回到出发点，找出一条这样的路线我们就称为最佳路 线。实际上这个问题就是设计成一个欧拉图，就是在欧拉图里寻找一条欧拉回路的问题。 本文内容主要讨论的是当图上没有奇点时，就是能够一笔画找出这条道路，而这条道路就 是欧拉回路，即是我们要找的最佳路线；当有两个奇点时，和有多个奇点时；找出一条欧 拉回路，即是最佳的路线。当遇到多个奇点并且是偶数对时，就运用奇偶点图上作业法消 去奇点的办法，然后找出一条欧拉回路。最后给出求邮递员行走路线的算法，并给出一些 简单的应用。66327

毕业论文关键词： 邮路；欧拉图；Fluery 算法；奇偶点

Chinese Postman Problem Algorithm and Its Application

ABSTRACT:In an

G (V, E) graph,  the postman to  go  through  every vertex,  and  through

each street at least once, that is, each side  e  has a non-negative weight  w(e) , but also to be

able to return to the starting point, find a route we Called the best route. In fact this problem is designed as an Euler diagram, that is, in Euleru map to find an Euler circuit. The main discussion of this article is that when there is no singularity on the graph, it is the ability to find the line, and this route is the Euler circuit, that is, we want to find the best route; when there are two odd points , And there are a number of singular points; find an Euler loop, that is, the best route when faced with a number of singular points and even pairs, the use of odd points on the map method to eliminate the singular approach, and then find Out of an Euler circuit. Finally, we give the algorithm of postman walking route and give some simple application.

Keywords: Post Road; Euler; Fleury algorithm; Odd point

目录

摘要 2

ABSTRACT 2

第一章 绪论 3

1.1 课题的目的及意义 3

1.2 国内外研究现状与发展趋势 3

1.3 基本概念及符号说明 6

1.3.1 基本概念 6

1.3.2 符号说明 7

1.4 用到的定理 7

第二章 中国邮递员问题与欧拉环 8

2.1 无奇点的邮路与一笔画、欧拉图 8

2.2 两个奇点的邮路 11

2.3 多个奇点的邮路 13

2.4 小结 16

第三章 中国邮递员的路线算法 16

3.1 Fleury 算法具体步骤 16

3.2 Fleury 算法原理 17

3.3 小结 18

第四章 中国邮递员的具体应用 18

应用一 18

应用二 19

总结 21

致谢 22

参考文献 23

附录 23

中国邮递员问题算法及其应用 

第一章 绪论

1.1