信息与计算科学毕业设计（论文）中国邮递员问题综述

1、信息与计算科学毕业设计（论文）-中国邮递员问题综述 本科毕业论 设计 题国邮递员问题综学 统计与数理学院 专 业 级 20071班 学 号 名 指导师 国邮递员问题综，问题图论邮递员递线关键词递 欧拉回路 最短路 Lingo一、引言图论应广泛运筹学广泛应学学制论论学电计个领.在实际产学问题图论理论来决.组织产为项务学间样衔产务.一个邮递员送信负责递务邮应该样线线国递员问题1960年我们从产实际个数学问题从实际问题来个递员应该选择条线负责的我们开始国递员问题国究过谓货员问题，个货员要个货问应该选择样条线. 题显归纳为货员问题，实递员须个点个.但是一般来说递员约二个点归纳为货员问题来决将是个规问题

2、，无决.但是，在仔细递员临问题后，我们发现这个问题点点较实际我们称这个问题为递线路问题1965年后国称为国递员问题.二、概念与原理一名邮递员带着发的邮件从邮发，经过发的个邮邮须过他辖范围内条选择递线邮递员尽这个问题国数学山东师学数学1962年首次提出的，因此在国际称为国邮递员问题图论语个连赋权图寻条该中的每条边该权数最说从的每条边条权数最实际们为对之间的关会纸点线画样图.8世纪时欧个风丽, 那里有七座桥.图1岛、右岸各有两桥连结两间陆地、各有一座桥连结.问个样桥桥过发点这个例是历7桥问题.现国个图1当发岛图当间传远个难题.1736年，数学欧统决这类问题.七桥问题数学欧17071783）的关.他

3、把具体七桥归为图2简单图七桥问题变个笔问题样从、中的某一点发，笔这个简单图笔开纸、各条线只画点图2一笔图点或数条线连点有两个点数条线连.欧: 如果一个络是连顶点个数0或2，那么它可以一笔则笔.定义 经过条边迹Euler迹闭Euler迹Euler回路或回路,含Euler回路的图Euler图.观地讲Euler图从顶点发边过发点种图边发点.1（1）是Euler图条连顶点皆偶.（2）是Euler图条连.（3）中有Euler迹条连有两个点.2 对连图GV，E），下列条 （1）G是一个欧图 （2）G的每一个节点数数 （3）G的边E可以分解为个“奇点”，与偶数条线相连的点叫“偶点”三、运名邮递员带着发的邮件

4、从邮发，经过发的个邮邮须过他辖范围内条选择递线邮递员尽这个问题国数学山东师学数学1962年首次提出的，因此在国际称为国邮递员问题图论语个连赋权图寻条该中的每条边该权数最说从的每条边条权数最是欧图则罗莱个欧不是欧图数节点则国递员问题的决难标给数节点连图寻权数路与哥尼斯堡7桥问题相联系的在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点与此相反，设为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图为欧拉图在一个图中，连接一个节点的边数称为该节点的度数对欧拉图，我们有下列结果：定理3 下列条件是相互等价的：

5、（1）是一个欧拉图； （2）的每一个节点的度数都是偶数； （3）的边集合可以分解为若干个回路的并 证明 ： 已知为欧拉图，则必存在一个欧拉回路回路中的节点都是偶度数 设中每一个节点的度数均为偶数若能找到一个回路使，则结论成立否则，令，由上每个节点的度数均为偶数，则中的每个节点的度数亦均为偶数于是在必存在另一个回路令，?由于为有限图，上述过程经过有限步，最后必得一个回路使 上各节点的度数均为零，即这样就得到的一个分解 设，其中（I 1,2,r）均为回路由于为连通图，对任意回路,必存在另一个回路与之相连，即与存在共同的节点现在我们从图G的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转

6、向另一个回路，?，这样一直走下去就可走遍的每条边且只走过一次,最后回到原出发节点，即为一个欧拉图利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了下面介绍一种求欧拉回路的算法即：弗罗莱算法算法步骤如下：（1）任取起始点 （2）设路已选出，则从E中选出边，使与相连，除非没有其它选择，仍应为连通的 （3）重复步骤（2），直至不能进行下去为止定理4 有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等 如果是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若不是欧拉图，即存在奇度数的节点，则中国由递员问题的解

7、决要困难得多本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法首先注意到，若图有奇数度节点，则的奇数度节点必是偶数个把奇数度节点分为若干对，每对节点之间在中有相应的最短路，将这些最短路画在一起构成一个附加的边子集令，即把附加边子集迭加在原图上形成一个多重图，这时G/中连接两个节点之间的边不止一条显然是一个欧拉图，因而可以求出的欧拉回路该欧拉回路不仅通过原图中每条边，同时还通过中的每条边，且均仅一次邮递员问题的难点在于当的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集 的权数为最小？为此有下列定理 定理 5 设为一个连通的赋权图，则使附加边子集的权

8、数为最小的充分必要条件是中任意边至多重复一次，且中的任意回路中重复边的权数之和不大于该回路总权数的一半必要性用反证法设存在一种奇节点集的配对，使其附加边子集权数 为最小若中有一条边重复次，由于为欧拉图，所以删去相应的二次重复边后仍为欧拉图这样，相应的附加边子集的权数将减小，这与为最小的假设矛盾这说明中的边均互不相同 其次，若中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在中删去这些重复边（注意：这些边均在中），而代之以该回路的其余部分的边再重复一次经过这种替代后所得到的边子集仍为附加子集，且，又产生矛盾 充分性设有两个附加边子集和，均使/和中每条边至多重复一次，且每个回路中的

9、重复边的权数和不大该回路权数的一半，我们来证明首先注意到，由和不相同的部分组成的图（记为）是由一个或若干个欧拉子图所组成的这是因为中每个节点的度数均为偶数，而和的公共边数也是偶数，故中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成的任何回路都由E/和E/中的边组成，而E/和E/在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于中的权数之和与属于中的边数之和必定相等，所以它就是最优附加边子集的权数，即和均为使附加边子集的权数达到最小的最优附加边子集.四 数型分析 由定理3可得一个寻找邮递员问题最优解的方法现举例如下： 图3 知邮递员要投递的

10、街道如图3示，试求最优邮路先找出奇节点：，奇节点进行配对，不妨把与，与，A3与B3，与配对，求其最短路显然它不是最优解下面我们根据定理3来进行调解图4第一次调整：删去多于一条的重复边，即与，与中的调整后，实际上成为与，与，与，与的配对，它们的最短路如图4示图5第二次调整：发现在回路 ， 中重复边的权数和为11，大于该回路权数20的一半因而调整时，把该回路的重复边删去，代之以重复其余部分，得图5可以看出，实际上是调整为与，与，与，与配对图6第三次调整：在图5中发现回路 ， 中重复边的权数和为7，大于该回路权数10的一半，因而删去原重复边（，）和（，），而添加（，），得到图6进行检查发现，既没有多

11、于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图6就是最优的附加边子集，而为欧拉图，因此，可以求得最优的路线为.五 优化模型 上述的邮递员问题，邮递员递围内条没别实际递过单线两边单时递问题.这样问题称为广义国邮递员问题.这广义国邮递员问题为个图问题. 类邮递员问题称为传统邮递员问题广义邮递员问题综为：给个连图个上有非负权寻的一个过个总权.对广义国邮递员问题，个数1条时已经条对应连图点进数数相从,存在回路（回路）.在此，如,则称是顶点进时的出向弧.可以证的顶点数为则每条条实现顶点进项数数相.根据以上分析，对的每条定义数变，表示弧上增加了条个图.类广义国邮递员显数规）:

12、min s.t.通过这广义国邮递员问题的递线.虑图国邮递员问题图8根据前面的模型讨论这一数邮递员问题对应数规lingo程序如下：minZ 2* x18+x81 +4* x87+x78 +5* x12+x21 +3* x89+x98 +6* x29+x92 +3* x67+x76 +4* x69+x96 +5* x32+x23 +4* x94+x49 +4* x56+x65 +9* x43+x34 +4* x54+x45 ;x21+x81-x12-x18 0;x12+x92+x32-x21-x29-x23 0;x23+x43-x32-x34 0;x34+x94+x54-x43-x49-x45 0

13、;x65+x45-x56-x54 0;x76+x96+x56-x67-x69-x65 0;x67+x87-x76-x78 0;x18+x78+x98-x81-x87-x89 0;x29+x49+x69+x89-x92-x94-x96-x98 0;x18+x81 1 ;x87+x78 1;x12+x21 1;x89+x98 1;x67+x76 1;x29+x92 1;x96+x69 1;x23+x32 1;X94+X49 1;X56+X65 1;X43+X34 1;X45+X54 1;表9运行lingo9.0得到结果如下Feasible solution found.Total solver i

14、terations: 6 Variable Value MINZ 88.00000 X18 0.000000 X81 1.000000 X87 2.000000 X78 0.000000 X12 1.000000 X21 0.000000 X89 0.000000 X98 3.000000 X29 0.000000 X92 1.000000 X67 0.000000 X76 2.000000 X69 1.000000 X96 0.000000 X32 0.000000 X23 2.000000 X94 0.000000 X49 3.000000 X56 0.000000 X65 1.00000

15、0 X43 0.000000 X34 2.000000 X54 1.000000 X45 0.000000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 1.000000 13 0.000000 14 2.000000 15 1.000000 16 0.000000 17 0.000000 18 1.000000 19 2.000000 20 0.0

16、00000 21 1.000000 22 0.000000 所以这一问题的最优解是其它，最小权为8.假定邮点V,则递线：注意这问题的递线.同理可以求得邮从点发时递线.当然，在本文之外还有很多涉及此问题的相关论题，我们还要不断努力，不断学习，为我国的邮递事业进到一点贡献.参考文献：1管梅谷 奇偶点图上作业法M.数学学报, 1960.3.2管梅谷 邮递员问题综述M.数学研究与评论1965.53李玮 、王雷 中国邮递员问题的DNA计算M 中国教育出版,2009.64许志国、桂湘云 运筹学（第三版）M清华大学出版社2008.75韩中庚. 用运筹学模型、方法计算M.清华大学出版,2007.96哈拉里 图

17、论 M 上海科技出版社 1980.97李念祖 关于中国邮递员问题的最有完全子图算法社J 2009.19 07 8吴杰 求解中国邮递员问题的一种思路J 科技资讯 2007,169冯俊文 中国邮递员问题的整数规划模型J ,2010.1210 金毅 对中国邮递员的理性分析 J, 科技经济市场 2009.5A review of the Chinese postman problem Gao KunAbstract: This article gives a conmprehensive review of the Chinese postman problem CPP , the use of op

18、erations research principles of graph theory, Euler circuit, by the Konigsberg problem associated with the first issue of a stroke, the postman problem into a graph theory-related model, using the shortest Road principle of making the shortest postman's delivery routes, and further discussed the actua