图和hamilton图的应.ppt

第三节 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中将边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是连通图，转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的增大，计算量将急剧增加，即使是大容量高速计算机也无法处理 旅行推销员问题的有效算法到底存在还是不存在？这是当今数学界的一个著名难题。