数学建模案例分析第9讲-行遍性问题课件_第1页
数学建模案例分析第9讲-行遍性问题课件_第2页
数学建模案例分析第9讲-行遍性问题课件_第3页
数学建模案例分析第9讲-行遍性问题课件_第4页
数学建模案例分析第9讲-行遍性问题课件_第5页
已阅读5页，还剩16页未读， 继续免费阅读

下载本文档

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

文档简介

1、数学建模案例分析第9讲 行遍性问题行 遍 性 问 题一、中 国 邮 递 员 问 题二、推 销 员 问 题三、建模案例：最佳灾情巡视路线（一） 欧 拉 图（二） 中 国 邮 递 员 问 题（一） 哈 密 尔 顿 图（二） 推 销 员 问 题7/18/2022数学建模7/18/2022数学建模 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割边G的边 是割边的充要条件是 不含在G的圈中 割边的定义：设G连通， E(G),若从G中删除边 后，图G- 不连通，则称边 为图G的割边7/18/2022数学建模 e3 v1 v2 v3 v4e1e2e4 e5e6欧 拉 图 e3 v1 v2

2、v3 v4 e1e 2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v17/18/2022数学建模e3 v1 v2 v3v4e1e2e4 e5e3 v1 v2 v3v 4 e1 e2e4 e5e6欧拉图 非欧拉图返回7/18/2022数学建模中国邮递员问题-定义7/18/2022数学建模中国邮递员问题-算法 Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有

3、边可选择为止.7/18/2022数学建模 v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e107/18/2022数学建模 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小7/18/2022数学建模v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e97/18/2022数学建模7/18/2022数学建模（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对7/18/2022数学建模返回7/18/20

4、22数学建模哈 密 尔 顿 图返回7/18/2022数学建模推销员问题-定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题7/18/2022数学建模定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳H圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长47/18/2022数学建模7/18/2022数学建模推销员问题近似算法：二边逐次修

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论