《三节Euler图和Hamilton图应用.ppt》由会员分享，可在线阅读，更多相关《三节Euler图和Hamilton图应用.ppt（16页珍藏版）》请在三一文库上搜索。
1、第三节 Euler图和 Hamilton 图的应用,邮递员从邮局出发，到他所负责的地段投寄信件。地段中的每条街至少经过一次。问应怎样选择投寄路线使所走的路程最短？,中国邮递员问题,1,1,1,1,1,1,2,1,1,1,2,2,2,2,2,2,3,3,2,中国邮递员问题是由我国的管梅谷教授在1960年首先提出的。,用图论的语言, 这一问题可表述为: 在一个赋权连通无向图G中，求一个权和最小的包含每条边至少一次的闭通路。这样的闭通路简称为最佳邮路。,若G是欧拉图，那么每一条欧拉闭迹即为一条最佳邮路。,易证可以用加重边的方法使任何连通图G转变成欧拉图,若不是欧拉图，则在每条邮路中必有边重复。在G中
2、将边e用k条重边代替且每一边都赋权W(e)，这样的过程称为加重边。,求最佳邮路的问题可转化为下列两个问题:,第2个问题可用弗劳瑞算法解决。 对于第1个问题埃德蒙斯(J.Edmonds)和约翰逊(L.Johnson)于1973年给出了一个有效算法。,(1)寻找权和最小重边集E, 使G+E是欧拉图.,(2)在G+E中找一条欧拉闭迹.,Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming 1973,5(1):88-124,算法： 如果G是连通
3、图，转2，否则返回无解并结束； 检查G中的奇点，构成图H的顶点集； 求出G中每对奇点之间的最短路径长度，作为图H对应顶点间的边权； 对H进行最小权匹配； 把最小权匹配里的每一条匹配边代表的路径，加入到图G中得到图G； 在G中求欧拉回路，即所求的最优路线。,求中国邮递员问题的一个简单算法 表上作业法,判定标准1 在最优邮递路线上，图中的每 一条边 至多有一条重复边。,判定标准2 在最优邮递路线上，图中每 一个圈的重复边的总权小于或者等于该 圈总权的一半。,两个判定标准,v8,v7,v6,v5,v4,v3,v2,v1,v10,v9,10,9,4,9,7,1,8,5,2,2,2,10,练习：,设有n个城市A1,A2,An, 每两个城市间都有直航的航班。一个推销员从A1乘飞机出发，每个城市都去一次，最后返回A1。任何两个城市的距离都是已知的，问应如何安排旅行路线使总路程最短？,旅行推销员问题(TSP),旅行推销员问题用图论的语言可叙述为: 在赋权完全图中，求权最小的哈密尔顿圈。,一个最直接的想法是将n阶完全图的(n-1)!个哈密尔顿圈全部排列出来，依次比较它们的权的大小。但这种想法在实际上是行不通的。因为随着n的增大，计算量将急剧增加，即使是大容量高速计算机也无法处理。 旅行推销员问题的有效算法到底存在还是不存在？这是当今数学界的一个著名难题。,