版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、行 遍 性 问 题,数学建模与数学实验,经济数学系数学建模研究室,行 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,三、建模案例：最佳灾情巡视路线,（一） 欧 拉 图,（二） 中 国 邮 递 员 问 题,（一） 哈 密 尔 顿 图,（二） 推 销 员 问 题,G的边e是割边的充要条件是e不含在G的圈中,割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边,欧 拉 图,巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1,欧拉道路：v1e1v2e2v3e5v1e4v4e3v3,欧拉巡回：v1e1v2e2v3e5v1e4v4e
2、3v3e6v1,欧拉图,非欧拉图,返回,中国邮递员问题-定义,中国邮递员问题-算法,Fleury算法-基本思想：从任一点出发，每当访问 一条边时，先要进行检查如果可供访问的边不只 一条，则应选一条不是未访问的边集的导出子图的 割边作为访问边，直到没有边可选择为止.,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在一些点对之间 引入重复边（重复边与它平行的边具有相同的权）， 使原图成为欧拉图，但希望所有添加的重复边的 权的总和为最小,（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对,返回,哈 密 尔 顿 图,返回,推销员问题-定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题,若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题,定义在加权图G=(V,E)中， （）权最小的哈密尔顿圈称为最佳H圈 （）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H回路，长22,最佳推销员回路，长4,
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026广东广州市白云区龙归学校（教师）招聘4人考试备考题库及答案解析
- 2026石嘴山市自然资源局招聘编外聘用制工作人员2人考试备考题库及答案解析
- 2025年河南省安阳市高职单招职业适应性测试考试试题及答案解析
- 2026辽宁抚顺市教育局直属学校校园招聘160人笔试备考试题及答案解析
- 2026广东清远市英德市中医院招聘事业编制专业技术人员12人笔试模拟试题及答案解析
- 2026北京大学实验动物中心招聘实验动物技术岗位人员1人考试参考试题及答案解析
- 2026福建宁德市古田县数字产业发展中心招聘紧缺急需人才1人笔试备考试题及答案解析
- 2026福建泉州鲤城区国有企业“鲤育贤才”招聘3人考试参考题库及答案解析
- 2026年郑州大学药物安全性评价研究中心招聘非事业编制（劳务派遣）工作人员2名考试备考试题及答案解析
- 2026江苏无锡市南方不锈钢物业管理有限公司招聘1人笔试模拟试题及答案解析
- 2026年郑州铁路职业技术学院单招职业适应性考试题库附答案解析
- 影视造型课件
- 2025年长沙卫生职业学院单招职业适应性测试题库附答案
- 2026年安全员-B证考试题及答案（1000题）
- 医疗机构纠纷预防培训的分层培训方案
- 2026届高三化学二轮复习+综合实验突破
- 开挖机劳务合同范本
- 邮政企业法律培训课件
- 中医妇科健康科普讲座
- 精神科院感难点
- 道路标线施工操作规程
评论
0/150
提交评论