




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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的增大,计算量的增大,计算量将急剧增加,即使是大容量高速计算机将
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 五年级数学上册思维训练计划
- 2025年能源企业技术人员培训计划
- 小学一年级安全环境整治计划
- 七年级上册生物教学计划
- 护理不良事件统计上报制度及流程
- 四年级英语课题研究推进计划
- 西安市东仪中学2025届九年级物理第一学期期末达标检测试题含解析
- 陕西省师范大附属中学2025届数学九上期末统考试题含解析
- 忻州师范学院《有限单元法》2023-2024学年第一学期期末试卷
- 重庆市西南大学附属中学2024年七上数学期末综合测试模拟试题含解析
- 2024年度智能电网控制系统采购与安装合同
- 新生儿早期基本保健(EENC)指南要点解读课件
- 雅佳AKAI-EWI5000-中文音色表
- DBJ51-T 184-2021 四川省预成孔植桩技术标准
- 单位委托存档人员聘用期内情况表
- 软件著作权设计说明书范本
- 1、校企合作办学制度
- 交通运输综合行政执法大队工作(岗位)职责汇编
- 员工人事档案目录
- T∕CAME 1-2019 家庭式产房建设标准
- 宁德碳纤维储氢瓶项目投资计划书_模板参考
评论
0/150
提交评论