中国邮路问题.ppt

《中国邮路问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.2、中国邮路问题邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。1、提出问题返回结束上图表示从R1-R15个街道交叉点，街道上的数字表示该街道的长度，单位为米。首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为G的环游。具有最小权的环游

2、称为G的最优环游，则中国邮路问题就是要在赋权图G中找一条最优环游。2、分析问题街道结构图由上构造右图3、解决问题返回结束寻找Euler图的最优环游的基本思路：（1）用双倍边方法求的一个Euler赋权母图，使达到最小。（2）用Fleury算法求得的Euler环游,就是图的环游；定理4.2.1（管梅谷，1960）设是一个连通的赋权图，是的一个Euler赋权生成母图，则当且仅当没有重复数大于2的边。并且的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半。返回结束奇偶点图上作业法（求最优环游算法）：(1)把中度为奇数的顶点两两配对，记为。对每个，中取一条路，将上的每一条边都

3、添加一条边，从而得到的一个赋权Euler生成母图。(2)去掉中关于的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。(4)用Fleury算法求的Euler环游。(3)检查的每一个回路，如果某个回路上多重边的权和超过此回路权和的一半，则将进行调整：删除，的边重数增加1。例1下图(a)给出赋权图，是的四个奇点。根据上述算法,求下图的最优环游。解：根据上述算法(1)，把和配对，和配对，取，并对中每条边各添加一条边；又取，并对中每条边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e)奇偶点图上

4、作业法缺陷：奇偶点图上作业法需要检查图中的每个回路。随着顶点个数和边数增加，回路个数增加。如下图一，图二。图一回路超过150个，图二回路至少有上千个。思考：如何求恰好有两个奇点的赋权图的最优环游？设恰好有两个奇点和，则可以利用2.2节求出的一条最短路，在中只要把中的每一条边中再添加一条边，加上权就可得Eluer图。可以证明的Eluer环游就是的最优环游。下左图的最优环游即为右图。思考：如何求恰好有个奇点的赋权图的最优环游？