中国邮路问题及其算法大学论文

PAGEPAGE24目录1引言 12中国邮路问题 12.1图的概念 12.2道路与回路 22.2.1基本概念 22.2.2欧拉回路 32.3中国邮路问题 32.3.1无向图的中国邮路问题 42.3.2有向图的中国邮路问题 63中国邮路问题的算法 83.1无向图的中国邮路问题的算法 83.1.1奇偶点图上作业法 83.1.2最小权匹配算法 103.1.3破圈法 123.2有向图的中国邮路问题的算法 144中国邮路问题在实际生活中的应用与推广 154.1无向图的中国邮路问题在实际生活中的应用 154.2有向图的中国邮路问题在实际生活中的应用 215结束语 23参考文献 24致谢 25中国邮路问题及其算法Xxxxxx系本xxxxx班xxxxxx指导教师：xxxxxxx摘要：本文利用图论中的相关概念阐述并解决中国邮路问题，通过比较不同路径，归纳总结，找到其具体算法，再利用上述方法找到的具体算法，求解实例，加以验证，然后将其推广到实际生活中，帮助人们快速找到欧拉回路，即找到省时，省力，省钱的最佳路线，对于图论教学及理论研究均有一定的指导意义。关键词：中国邮路，欧拉回路，最佳路线。China'spostalproblemanditsalgorithmXxxxxxxxxClassxxxxx,TheDepartmentofmathematicsInstructor:xxxxxxAbstract:inthispaper,usingtherelevantconceptsinthispaper,thegraphtheoryandsolvetheproblemofChinapostroad,throughcomparingthedifferentpaths,sumup,finditsspecificalgorithm,usingtheabovetofindthespecificalgorithm,solvingtheinstance,verified,andthentopromoteittoreallife,tohelppeoplequicklyfindeularloop,namelyfindtosavetime,effort,savemoney,thebestwayofthegraphtheoryteachingandtheoreticalresearchhavecertainguidingsignificance.Keywords:Chinapostroad,eularcircuit,thebestroute.1引言中国邮路问题是我国著名图论学者管梅谷教授首先提出并解决的。它起初为了帮助邮递员选择一条合适道路，使其在完成任务的同时所走路程最短，后来其方法在实际生产生活中有广泛的应用，如邮政部门，扫雪车线路，洒水车路线，警车巡逻路线等，具有很强的实用价值，本文紧抓其实质与核心，通过对传统中国邮路问题研究方法的归纳总结，帮助人们快速找出欧拉回路，实现了将数学知识应用于实际生活中，服务于人类。2中国邮路问题2.1图的概念定义1二元组称为图，其中是非空集合，称为结点集，是诸结点之间边的集合，常用表示图。(1)图可分为有限图与无限图两类，现只讨论,都是有限集，给定某个图，如果不加特别说明，认为，，即结点数，边数。(2)图的边可以是有方向的，也可以是无方向的，它们分别称为有向边和无向边，用表示。定义2的某结点所关联的边数称为该结点的度，用表示。定义3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。性质1设有个结点，条边，则。性质2中度为奇数的结点必为偶数个。定义4若图的每条边都赋以一个实数作为该边的权，则称是赋权图，特别地，如果这些权都是正实数，就称是正权图，权可以表示该边的长度，时间，费用或容量等，如下图2.1所示：图2.12.2道路与回路2.2.1基本概念定义1有向图中，若边序列，其中，满足是的终点,是的始点，就称是的一条有向道路，如果的终点是的始点，则称是的一条有向回路。如果中的边没有重复出现，则分别称为简单有向道路和简单有向回路，进而，如果中结点也不重复出现，又分别称它们为初级有向道路或初级有向回路，简称为路或回路。显然，初级有向道路（回路）一定是简单有向道路（回路）。如下图2.2.1(a)所示：图2.2.1(a)边序列是有向道路；边序列是有向回路；边序列是简单有向道路；边序列是简单有向回路；边序列是初级有向道路；边序列是初级有向回路。定义2无向图中，若点边交替序列满足,是的两个端点，则称是中的一条链或道路；如果,则称是中的一个圈或回路。如下图2.2.1(b)所示：图2.2.1(b)边序列是道路；边序列是回路；边序列是简单道路；边序列是简单回路；边序列是初级道路；边序列是初级回路。定义3设是无向图，若的任意两结点之间都存在道路，则称是连通图，否则称为非连通图。2.2.2欧拉回路定义1对于连通的无向图，若存在一简单回路，它通过的所有边，则这回路称为的Euler回路。定理1无向连通图存在欧拉回路的充要条件是中各结点的度都是偶数。推论1若无向连通图中只有2个度为奇数的结点，则存在欧拉道路。推论2若有向连通图中各结点的正、负度相等，则存在有向欧拉回路。2.3中国邮路问题中国邮路问题，它是由中国数学家管梅谷教授首先提出而得名。设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，要求所走的路径最短，当然如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求的路径，如若不然，即存在度数为奇数的顶点时，必然有些街道需要走多于1遍，如何寻求最短的路？（基本思路：根据欧拉圈原理，用奇偶点图上作业法，使邮递路线为最短）现将中国邮路问题用图论的语言描述如下：设是连通图，而且对于所有的,都赋以权，求以点出发，通过所有边至少一次，最后返回点的回路，使得达到最小。2.3.1无向图的中国邮路问题邮递员从邮局出发，走完投递线路后又回到邮局，这就要求邮递员的行走路径必须是欧拉圈，但是由于城市街道及邮递点组成的图有三种基本类型，相应的就有三种类型线路，不管何种类型，归根到底，都要设法使之形成欧拉圈。(1)图里没有奇次定点。即中各结点的度都是偶数，那么一定有欧拉回路，显然任何一条欧拉回路都是该问题的解。如下图2.3.1(a)所示：图2.3.1(a)投递路线为：或者可为：这时没有重复行走的街道，当然邮路最短。(2)图中只有2个结点,的度是奇数，则一定存在从到的一条欧拉道路，它经过了的各边一次。在中再找一条从到的最短道路，则中存在欧拉回路。这样中的欧拉回路，即对应于中的边重复一次而其余边只过一次的回路是一条中国邮路，即最佳邮路。如下图2.3.1(b)所示：图2.3.1（b）如图，，是奇次顶点，因此要构成一个欧拉回路，线路必须重复走一次，这样存在许多重复走的方案，例如;;;等。我们计算一下重复走的长度分别为4，6，5，5；当然需要重复走的线路以为最好，故巧加边，是使其形成欧拉回路的方法，故此时线路为.总长度为21，且此路线是最短的。(3)图中度为奇数的结点数多于2个，则需要添加很多条边，才能形成欧拉回路，且有几对奇次顶点，就要加几条边，此时巧加边问题更加重要。如下图2.3.1(c)：图2.3.1(c)如图，有8个奇次顶点，它们是,,,,,,,.如何巧妙地把这8个奇次顶点恰当地组合成4对呢？我们参照上一题的例子，便可将8个奇次顶点配成以下4对：,,,.这是必须重复走的最短线路，且长度为11，最优投递路线总长为60，其中一条最佳路线为2.3.2有向图的中国邮路问题(1)图中含有正度或负度为0的结点，此时不存在最佳邮路。如图2.3.2(a)所示：图2.3.2(a)(2)图中各结点的正，负度相等，此时中一定存在有向欧拉回路。它过每边一次且仅一次，因此任意一条欧拉回路都是中国邮路。如下图2.3.2(b)所示：图2.3.2(b)(3)图不对称，即存在一些结点，，其中的值是以为始点的边的数目，的值是以为终点的边的数目。不妨设，由于邮递员要经过进入的每条边，因此他一定要重复走以为始点的某条边。设表示边的重复次数，表示该边的权，那么中国邮路要选择重复一些边后存在有向欧拉回路，并且使为最小的一个解，显然此时满足，即.(i)若，表示邮路中要次重复经过所发出的一些边，或者说可供应个单位量。(ii)若,表示邮路中要次重复经过进入的一些边，或者说可接收个单位量。(iii)若,则称是中间结点。由于，所以，这样可以逐次保证每个可供应点经过一些边向某个接收点供应一个单位量，最后达到平衡，或者说这些道路上的边出现重复，最后得到的图是有向欧拉图，若这些重复边的总长最小，它即是最佳邮路。例1求下图的中国邮路。解此题显然是有向中国邮路问题中的不对称型，故(1)各结点的为，，，。(2)构造如下图2.3.2(c):图2.3.2(c)图2.3.2(d)(3)得到2条总和最小的道路,；，;故.这样边重复2次，边重复1次，得图2.3.2(d)，其中虚线边表示重复1次。(4)图2.3.2(d)是欧拉图，其中一条欧拉回路，如就是最佳邮路。3中国邮路问题的算法3.1无向图的中国邮路问题的算法3.1.1奇偶点图上作业法(1)把中所有奇度数顶点配成对，将每对奇度数顶点之间的一条路上的每边改为二重边，得到一个新图,新图中没有奇度数顶点，即为多重Euler图。(2)若中某一对顶点之间有多于2条边连接，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点，直到每一对相邻顶点至多由2条边连接，得到图。(3)检查的每一个圈,若某一个圈上重复边的权和超过此圈权和的一半，则将进行调整。重复这一过程，直到对的所有圈，其重复边的权和不超过此圈权和的一半，得到图。(4)求的Euler回路。例2求下图所示图的中国邮路。图G解图中有6个奇度数顶点,,,,,.把它们配成三对：与,与,与，在图中，取一条与的路，把边,,作为重复边加入图中；再取与之间一条路，把边,,作为重复边加入图中，在和之间加一条重复边，如图(2)，这个圈没有奇度数点，是一个Euler图。(2)(3)在图(2)中，顶点与之间有三条重边，去掉其中两条，得到图(3)，该图仍是一个Euler图。在图(3)中，圈的总权为24，而圈上重复边的权和为14，大于该圈总权的一半，于是去掉边和上的重复边，而在和上加入重复边，此时重复边的权和为10，小于该圈总权的一半。同理，圈的总权和为15，去掉边和上的重复边，在边和上加重复边，如下图(4)：(4)(5)图(4)中，圈的总权为15，而重复边的权和为8，从而调整为图(5)。图(5)中,圈的总权为36,而重复边的总权为20,继续调整为图(6)：（6）经检验，图(6)为最优方案，其中一条欧拉回路就是最佳邮路。3.1.2最小权匹配算法(1)确定中度为奇数的结点，构成。(2)求各结点在中的最短路径及其长度。(3)对的结点进行最小权匹配，即选出个,保证每个结点在中只出现一次，同时满足这些的总和最小。(4)在最小权匹配里各所对应的路径中的诸边在中重复一次，得到。(5)是欧拉图，它的一条欧拉回路即为最优解。例3求下图所示图的中国邮路。解显然此题属于无向图的中国邮路问题，故(1)首先找到奇数结点，。(2)求各结点在中的最短路径及长度，，；，；，；，；，；，；，；，；，；，；，；，；，；，；，.(3)对的结点进行最小权匹配，得最佳匹配,,。(4)在最小权匹配里各所对应的路径中的诸边在中重复一次，得到下图。(5)是欧拉图，故它的一条欧拉回路即为最优解。3.1.3破圈法(1)奇点处作出标记如加“*”或“o”;(2)求该图的最小树（用破圈法，尽可能多的保留与奇点相连的边）；(3)在最小树上的奇点处添加重复边，以消灭奇点；(4)回到原问题，且按判优准则检验与调整，直至最优。注1最小生成树的求法：设是连通加权简单图，若不是树，则中必有回路，我们删去中含于某回路内权最大的一条边，所得图记为，是的连通生成子图，下一步，若不是树，又从的某回路内删去权最大的一条边，如此下去，最后不能按上述方法删边时，得到的图便是的一棵生成树，即是的最小生成树。例4求下面图中的最优邮路。解显然此题属于无向图的中国邮路问题，故(1)先在图中找到奇点，并记上“o”，如图(1)：（1）(2)求出该图最小树，如图(2)：（2）(3)在最小树上添加重复边，以消灭奇点，如图(3)：(3)(4)经检验，此已是最优解。此题的一条最优路线为3.2有向图的中国邮路问题的算法对称有向图的中国邮路算法较为简单，下面只研究非对称有向图的中国邮路算法，算法如下：(1)计算各结点的正，负度，求出，且。(2)添加一个超发点，对满足的结点，加入条有向边，权均为0；添加一个超收点，对满足的结点，加入条有向边，权均为0，得到图。(3)在中求条过以，为两端点的形如，每边一次且仅一次的总和最小的道路，记下中各边在这些道路中的重复次数。(4)计入各边的重复次数，中存在有向欧拉回路，其中一条即为解。例5求下图的中国邮路。解显然此题属于非对称有向图的中国邮路问题，故(1)先求各结点的为，，，(2)构造如下图(a)：(a)(3)得到2条总和最小的道路,；,;.这样边重复2次，边重复1次，得下图，其中虚线边表示重复1次。(4)上图即为欧拉图，其中一条欧拉回路如就是最佳邮路。4中国邮路问题在实际生活中的应用与推广4.1无向图的中国邮路问题在实际生活中的应用例6如下图(1)所示是忻州师范学院主区俯视图，图(2)是校内主干道的简略图，其中每条道路上至少有一个垃圾筒，收垃圾大叔每天需将校内所有的垃圾倒掉，下图中各边上的数字表示在此条路上完成任务所需时间（单位为分钟），问如何设计路线才能使大叔在完成任务的同时，所用时间最短？

(1)(2)分析我们把这个问题抽象成上图(2)所示，其中的结点表示几条相交道路的交点，各道路可用交点间的边表示，于是此问题就等价于图中是否存在经过图的每边一次且仅一次的闭迹问题。方法一用奇偶点图上作业法解在中有6个奇度数顶点,,,,,.把它们配成三对:与,与,与.在中，取一条连接与的路，并把边，作为重复边加入图中；再将与间一条路，把边，作为重复边加入图中，在与之间加一条重复边，如下图(a)中，这个图中没有奇度数点，是一个Euler图。(a)(b)在图(a)中，顶点，间有三条重边，去掉其中两条，得到图(b)，该图仍是一个Euler图。在图(b)中，圈的总权为6，而重复边的权和为2，小于该圈总权的一半；圈的总权为11，而重复边的权和为4，小于该圈总权的一半；圈的总权为8，而重复边的权和为2，小于该圈总权的一半；圈的总权为12，而重复边的权和为6，等于该圈总权的一半；圈的总权为16，而重复边的权和为8，等于该圈总权的一半；圈的总权为20，而重复边的权和为6，小于该圈总权的一半。由此看来，在每个圈上，都满足重复边的权和不超过此圈权和的一半，故图(b)为最优方案，其中一条欧拉回路即为最佳邮路，如即为一条最优邮路，且最短时间为49。方法二最小权匹配算法解显然此题属于无向图的中国邮路问题，故(1)先找出奇数结点；(2)再求各结点在中的最短路径及长度，，；，；，；，；，；，；，；，；，；，；，；，；，；，；，。对的结点进行最小权匹配，得最佳匹配为与,与,与,在最小权匹配里各所对应的路径中的诸边在中重复一次，得到上图(b)，且其为欧拉图，故它的一条欧拉回路即为最优邮路。方法三用破圈法来求解此题解显然此题属于无向图的中国邮路问题，故(1)先在图中找出奇点，并记上“o”,如下图(a)：(2)求出该图最小树，如下图(b)：(a)(b)(3)在最小树上添加重复边，以消灭奇点,如图(c)：(c)(4)经检验，此解已是最优解，其中任意一条欧拉回路即为最优解，如即为解，且最短时间为49。例7下图是忻州师院校内某超市的内部过道，刚刚开学时，某同学需要购买的物品比较多，下图中的数字表示在此货架上寻找自己所需物品的时间（单位为分钟），问若他能一次性购齐所有物品，如何规划路线能使其所用时间最短？分析本题用上述的三种方法均可求解，下面用破圈法为例解决此题。解(1)先找到图中的奇点，并记上“o”，如图(a)所示：(a)(2)求出该图的最小树，如图(b)所示：（方法用破圈法）(b)(3)在最小树上添加重复边，以消灭奇点,如图(c)：(c)(4)经检验，此解已是最优解，如就是一条最优中国邮路，且最短用时为41。4.2有向图的中国邮路问题在实际生活中的应用例8实例图仍为忻州师范学院，校内由于道路较窄，每到开学季，进入校内的车辆较多，故每条道路都为单行线，其方向如图所示，某家长想开车环游整个校园，问如何规划路线才能使其在不违反规定的条件下，将校内每条道的风景都领略到呢？解显然此题属于非对称有向图的中国邮路问题，故(1)求得各结点的为，，，。(2)构造如图(b)：(b)(3)得到4条总和最小的道路,;,;,;,;.这样边,各重复4次，边,,各重复3次，边,各重复2次，边,各重复1次，得到下图(c)，其中虚线边数表示重复次数。(c)(4)图(c)是欧拉图，其中一条欧拉回路