第三节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 1

4、973,5(1):88-124算法：算法：假设假设G是连通图，转是连通图，转2，否那么前往无解并终了；，否那么前往无解并终了；检查检查G中的奇点，构成图中的奇点，构成图H的顶点集；的顶点集；求出求出G中每对奇点之间的最短途径长度，作为图中每对奇点之间的最短途径长度，作为图H对应顶点间的边权；对应顶点间的边权；对对H进展最小权匹配；进展最小权匹配；把最小权匹配里的每一条匹配边代表的途径，参把最小权匹配里的每一条匹配边代表的途径，参与到图与到图G中得到图中得到图G；在在G中求欧拉回路，即所求的最优道路。中求欧拉回路，即所求的最优道路。求中国邮递员问题的一个简单算法求中国邮递员问题的一个简单算法表上

5、作业法表上作业法断定规范断定规范1 在最优邮递道路上，图中的每在最优邮递道路上，图中的每一条边一条边 至多有一条反复边。至多有一条反复边。断定规范断定规范2 在最优邮递道路上，图中每在最优邮递道路上，图中每一个圈的反复边的总权小于或者等于该一个圈的反复边的总权小于或者等于该圈总权的一半。圈总权的一半。 两个断定规范两个断定规范v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2

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