1、行 遍 性 问 题数学建模与数学实验后勤工程学院数学教研室行 遍 性 问 题一、中 国 邮 递 员 问 题二、推 销 员 问 题三、建模案例：最佳灾情巡视路线（一） 欧 拉 图（二） 中 国 邮 递 员 问 题（一） 哈 密 尔 顿 图（二） 推 销 员 问 题V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中 割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边e3v1v2v3v4e1e2e4e5e6欧 拉 图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v
2、3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图返回中国邮递员问题-定义中国邮递员问题-算法 Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是，在一些点
3、对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对返回哈 密 尔 顿 图返回推销员问题-定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳H圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4推销员问题近似算法：二边逐次修正法：例对以下完备图，用二边逐次修正法求较优H圈返回
