图和hamilton图的应

《图和hamilton图的应》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节Euler图和Hamilton图的应用邮递员从邮局出发，到他所负责的地段投寄信件。地段中的每条街至少经过一次。问应怎样选择投寄路线使所走的路程最短？中国邮递员问题1111112111222222332中国邮递员问题是由我国的管梅谷教授在1960年首先提出的。用图论的语言,这一问题可表述为:在一个赋权连通无向图G中，求一个权和最小的包含每条边至少一次的闭通路。这样的闭通路简称为最佳邮路。若G是欧拉图，那么每一条欧拉闭迹即为一条最佳邮路。易证可以用加重边的方法使任何连通图G转变成欧拉图若不是欧拉图，则在每条邮路中必有边重复。在G中将边e用k条重边代替且每一边都赋权W(e)，这样的过

2、程称为加重边。求最佳邮路的问题可转化为下列两个问题:第2个问题可用弗劳瑞算法解决。对于第1个问题埃德蒙斯(J.Edmonds)和约翰逊(L.Johnson)于1973年给出了一个有效算法。(1)寻找权和最小重边集E’,使G+E’是欧拉图.(2)在G+E’中找一条欧拉闭迹.Jack EdmondsandEllis L. Johnson.Matching,EulertoursandtheChinesepostman.MathematicalProgramming1973,5(1):88-124算法：如果G是连通图，转2，否则返回无解并结束；检查G中的奇点，构成图H的顶点集；求出G中每对奇

3、点之间的最短路径长度，作为图H对应顶点间的边权；对H进行最小权匹配；把最小权匹配里的每一条匹配边代表的路径，加入到图G中得到图G’；在G’中求欧拉回路，即所求的最优路线。求中国邮递员问题的一个简单算法－－表上作业法判定标准1在最优邮递路线上，图中的每一条边至多有一条重复边。判定标准2在最优邮递路线上，图中每一个圈的重复边的总权小于或者等于该圈总权的一半。两个判定标准v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v225594

4、4346443v9v7v6v3v4v5v8v1v2255944346443v9v8v7v6v5v4v3v2v1v10v910949718522210练习：设有n个城市A1,A2,…,An,每两个城市间都有直航的航班。一个推销员从A1乘飞机出发，每个城市都去一次，最后返回A1。任何两个城市的距离都是已知的，问应如何安排旅行路线使总路程最短？旅行推销员问题(TSP)旅行推销员问题用图论的语言可叙述为:在赋权完全图中，求权最小的哈密尔顿圈。一个最直接的想法是将n阶完全图的(n-1)!个哈密尔顿圈全部排列出来，依次比较它们的权的大小。但这种想法在实际上是行不通的。因为随着n的增大，计算量将急

5、剧增加，即使是大容量高速计算机也无法处理。旅行推销员问题的有效算法到底存在还是不存在？这是当今数学界的一个著名难题。