《数学建模案例分析行遍性问题》由会员分享,可在线阅读,更多相关《数学建模案例分析行遍性问题(21页珍藏版)》请在金锄头文库上搜索。
1、 行 遍 性 问 题数学建模与数学实验Date数学建模行 遍 性 问 题一、中 国 邮 递 员 问 题二、推 销 员 问 题三、建模案例:最佳灾情巡视路线(一) 欧 拉 图(二) 中 国 邮 递 员 问 题(一) 哈 密 尔 顿 图(二) 推 销 员 问 题Date数学建模Date数学建模73123412 4 5566789割边G的边 是割边的充要条件是 不含在G的圈中 割边的定义:设G连通, E(G),若从G中删除边 后, 图G- 不连通,则称边 为图G的割边Date数学建模e3v1v2v3v4e1e2e4 e5e6欧 拉 图e3v1 v2v3v4e1e 2e4e5巡回:v1e1v2e2v3
2、e5v1e4v4e3v3e5v1欧拉道路:v1e1v2e2v3e5v1e4v4e3v3欧拉巡回:v1e1v2e2v3e5v1e4v4e3v3e6v1Date数学建模e3v1v2v3v4e1e2e4 e5 e3v1v2v3v 4e1e2e4 e5e6欧拉图非欧拉图返回 Date数学建模中国邮递员问题-定义Date数学建模中国邮递员问题-算法Fleury算法基本思想:从任一点出发,每当访问 一条边时,先要进行检查如果可供访问的边不只 一条,则应选一条不是未访问的边集的导出子图的 割边作为访问边,直到没有边可选择为止.Date数学建模v7e3v1v2v3v4e1e2e4 e5v5e6e6e 7e8e
3、9e10Date数学建模若G不是欧拉图,则G的任何一个巡回经过某 些边必定多于一次解决这类问题的一般方法是:在一些点对之间 引入重复边(重复边与它平行的边具有相同的权), 使原图成为欧拉图,但希望所有添加的重复边的 权的总和为最小 Date数学建模v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9Date数学建模Date数学建模()求出G1的最小权理想匹配M,得到奇次顶点的最佳配对Date数学建模返回 Date数学建模哈 密 尔 顿 图返回Date数学建模推销员问题-定义流动推销员需要访问某地区的所有城镇,最后 回到出发点问如何安排旅行路线使总行程最小 这就是推销员问题若用顶点表示城镇,边表示连接两城镇的路 ,边上的权表示距离(或时间、或费用),于是 推销员问题就成为在加权图中寻找一条经过每个 顶点至少一次的最短闭通路问题Date数学建模定义 在加权图G=(V,E)中, ()权最小的哈密尔顿圈称为最佳H圈 ()经过每个顶点至少一次的权最小的闭通路称 为最佳推销员回路一般说来,最佳哈密尔顿圈不一定是最佳推销员回路 ,同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路,长22最佳推销员回路,长4Date数学建模Date数学建模推销员问题近似算法:二边逐次修正法:Date数学建模例 对以下完备图,用二边逐次修正法求较优H圈Date数学建模返回 Date数学建模