图和Hamilton图的应.ppt_第1页
图和Hamilton图的应.ppt_第2页
图和Hamilton图的应.ppt_第3页
图和Hamilton图的应.ppt_第4页
图和Hamilton图的应.ppt_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第三节 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的增大，计算量将急剧增
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论