数学建模案例分析第9讲行遍性问题.ppt

数学建模 * 行 遍 性 问 题 数学建模与数学实验 行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9 割边 G的边 是割边的充要条件是 不含在G的圈中． 割边的定义：设G连通， E(G),若从G中删除边 后，图G-{ }不连通，则称边 为图G的割边． e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 欧 拉 图 e3 v1 v2 v3 v4 e1 e 2 e4 e5 巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1 欧拉道路：v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回： v1e1v2e2v3e5v1e4v4e3v3e6v1 e3 v1 v2 v3 v4 e1 e2 e4 e5 e3 v1 v2 v3 v 4 e1 e2 e4 e5 e6 欧拉图 非欧拉图 返回 中国邮递员问题-定义 中国邮递员问题-算法 Fleury算法基本思想：从任一点出发，每当访问 一条边时，先要进行检查．如果可供访问的边不只 一条，则应选一条不是未访问的边集的导出子图的 割边作为访问边，直到没有边可选择为止. v7 e3 v1 v2 v3 v4 e1 e2 e4 e5 v5 e6 e6 e 7 e8 e9 e10 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次． 解决这类问题的一般方法是：在一些点对之间 引入重复边（重复边与它平行的边具有相同的权）， 使原图成为欧拉图，但希望所有添加的重复边的 权的总和为最小．　 v7 e3 v1 v2 v3 v4 e1 e2 e4 e5 v5 v6 e6 e7 e8 e9 （３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对． 返回 哈 密 尔 顿 图 返回 定义１　设G=(V,E)是连通无向图 （１）经过G的每边至少一次的闭通路称为巡回． （２）经过G的每边正好一次的巡回称为欧拉巡回． （３）存在欧拉巡回的图称为欧拉图． （４）经过G的每边正好一次的道路称为欧拉道路． 定理１　对于非空连通图G，下列命题等价： （１）G是欧拉图． （２）G无奇次顶点． （３）G的边集能划分为圈． 推论１　设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点． 邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是中国邮递员问题. 若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为最佳巡回． 1. G是欧拉图 此时G的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回． Fleury算法：求欧拉图的欧拉巡回. Fleury算法—算法步骤： （１）任选一个顶点v0，令道路w0=v0. （２）假定道路wi=v0e1v1e2…eivi已经选好，则从E\{e1,e2,…,ei}中选 一条边ei+1，使： a）ei+1与vi相关联 b）除非不能选择，否则一定要使ei+1不是Gi=G[E-{e1,e2,…,ei}] 的割边． （３）第（２）步不能进行时就停止． 2. G不是欧拉图 情形１　G正好有两个奇次顶点 （１）用Dijkstra算法求出奇次顶点u与v之间的最短路径P． （２）令G*=GP，则G*为欧拉图. （３）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回． 情形２　G有２n个奇次顶点（n２） Edmonds最小对集算法： 基本思想： 先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回． 算法步骤： （１）用Floyd算法求出所有奇次顶点之间的最短路径和距离． （２）以G的所有奇次顶点为顶点集（偶数个元素），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1． （４）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*． （５）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回． 定义 设图G =（V，E），ME，若M的边互不相邻，则称M是G 的一个匹配.