三节Euler图和Hamilton图应用ppt课件

1、 第三节第三节 Euler图和图和 Hamilton 图的应用图的应用 邮递员从邮局出发，到他所负责的地邮递员从邮局出发，到他所负责的地段投寄信件。地段中的每条街至少经过段投寄信件。地段中的每条街至少经过一次。问应怎样选择投寄路线使所走的一次。问应怎样选择投寄路线使所走的路程最短？路程最短？中国邮递员问题中国邮递员问题1111112111222222332 中国邮递员问题是由我国的管梅谷教授中国邮递员问题是由我国的管梅谷教授在在1960年首先提出的。年首先提出的。 用图论的语言用图论的语言, 这一问题可表述为这一问题可表述为: 在一在一个赋权连通无向图个赋权连通无向图G中，求一个权和最中，求一

2、个权和最小的包含每条边至少一次的闭通路。这小的包含每条边至少一次的闭通路。这样的闭通路简称为最佳邮路。样的闭通路简称为最佳邮路。 若若G是欧拉图，那么每一条欧拉闭迹即为一是欧拉图，那么每一条欧拉闭迹即为一条最佳邮路。条最佳邮路。 易证可以用加重边的方法使任何连通图易证可以用加重边的方法使任何连通图G转转变成欧拉图变成欧拉图 若不是欧拉图，则在每条邮路中必有边重复。若不是欧拉图，则在每条邮路中必有边重复。在在G中将边中将边e用用k条重边代替且每一边都赋权条重边代替且每一边都赋权W(e)，这样的过程称为加重边。，这样的过程称为加重边。 求最佳邮路的问题可转化为下列两个问题求最佳邮路的问题可转化为下

3、列两个问题: 第第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-

4、124算法：算法：如果如果G是连通图，转是连通图，转2，否则返回无解并结束；，否则返回无解并结束；检查检查G中的奇点，构成图中的奇点，构成图H的顶点集；的顶点集；求出求出G中每对奇点之间的最短路径长度，作为图中每对奇点之间的最短路径长度，作为图H对应顶点间的边权；对应顶点间的边权；对对H进行最小权匹配；进行最小权匹配；把最小权匹配里的每一条匹配边代表的路径，加把最小权匹配里的每一条匹配边代表的路径，加入到图入到图G中得到图中得到图G；在在G中求欧拉回路，即所求的最优路线。中求欧拉回路，即所求的最优路线。求中国邮递员问题的一个简单算法求中国邮递员问题的一个简单算法表上作业法表上作业法判定标准判定

5、标准1 在最优邮递路线上，图中的每在最优邮递路线上，图中的每一条边一条边 至多有一条重复边。至多有一条重复边。判定标准判定标准2 在最优邮递路线上，图中每在最优邮递路线上，图中每一个圈的重复边的总权小于或者等于该一个圈的重复边的总权小于或者等于该圈总权的一半。圈总权的一半。 两个判定标准两个判定标准v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9

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