行遍性问题-最佳灾情巡视路线第9讲行遍性

1、 数学建模与数学实验行遍性问题行遍性问 题一、中 国 邮 递 员 问 题 图（一）（二） 中 国 邮 递 员 问 问 题二、 图（一） 问 题（二）三、建模案例：最佳灾情巡视路线题定义 设图 G =（V，E）， M E，若 M则称 M 是 G 的一个匹配.的边互不相邻，若顶点 v 与 M 的一条边关联，则称 v 是 M饱和的设 M 是 G 的一个匹配，若 G 的每个顶点都是 M饱和的，则称 M 是 G 的理想匹配.割边的定义：设G连通，eE(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边e1v1v2e2V5割边e4e8e7e6vV64ve9V73G的边e是割边的充要条件是e不含

2、在G的圈中e5e3图定义 设 G=(V,E)是连通无向图（）经过 G 的每边至少一次的闭通路称为巡回（）经过 G 的每边正好一次的巡回称为巡回（）存在巡回的图称为图（）经过 G 的每边正好一次的道路称为道路e1v1e1v2e2v1v2e2e4e4vv44vv33道路：v1e1v2e2v3e5v1e4v4e3v3巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e6e5 e3e5e3定理 对于非空连通图 G，下列命题等价：（）G 是图（）G 无奇次顶点（）G 的边集能划分为圈e1v1e1v2e2v1v2e2e4e4vv44vv33

3、图非图道路的充要条设 G 是非平凡连通图，则 G 有推论件是 G 最多只有两个奇次顶点中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行邮递员问题.程最短的路线这就若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区一个赋权连通无向图中国邮递员问题转化为：在一个非负连通图中，寻求一个权最小的巡回这样的巡回称为最佳巡回中国邮递员问题-算法图1、G 是G此时的任何一个巡回便是最佳巡回问题归结巡回为在图中确定一个Fleury 算法：求图的巡回Fleury算法-基本：从任一点出发，每当一条边时，先

4、要进行检查如果可供的边不只一条，则应选一条不是未的边集的导出子图的边，直到没有边可选择为止.割边作为Fleu ry 算法 算法步骤 ：（）任选一个顶点 v 0 ，令道路 w 0 =v 0（）假定道路 wi=v 0 e 1 v 1 e 2 eivi 已经选好，则从 Ee 1 ,e 2 , ,ei中选 一条边 ei+ 1 ，使： a） ei+1与 vi 相关联 b） 除非不能选择，否则一定要使的割边 ei+1不是 G i=G E-e 1,e 2, ,ei（）第（ ）步不能进行时就停止 e1v1v2e2e10V5e4e8e7e6vV64ve9V732、G 不是图若G不是图，则G的任何一个巡回经过某些

5、边必定多于一次解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为图，但希望所有添加的重复边的权的总和为最小情形 G 正好有两个奇次顶点（）用 Dijkstra 算法求出奇次顶点 u 与 v 之间的最短路径 P（）令 G*=G P，则 G*为（）用 Fleury 算法求出 G*的图巡回，这就是 G 的最佳巡回e1v1v2V5e4e2e8e7e6vV64ve9V73情形 G 有n 个奇次顶点（n ）Edmonds 最小对集算法：基本先将奇次顶点配对，要求最佳配对，即点对之间距离总和图 G*，G*最小再沿点对之间的最短路径添加重复边得的巡回便是原图的最佳

6、巡回算法步骤：（）用 Floyd 算法求出的所有奇次顶点之间的最短路径和距离G（）以的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图 G 中的最短距离，将此完备图记为 G1（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对图 G*（）在 G 中沿配对顶点之间的最短路径添加重复边得（）用 Fleury 算法求出 G*的巡回，这就是 G 的最佳巡回例 求右图所示投递区的一条最佳邮递路线1图中有 v4、v7、v8、v9 四个奇次顶点用dyo Fl 算法求出它们之间的最短路径和距：离4v4d,7v)v5Pv 4 vv73v8,2 v(7,d4,v8 vv) vP PP PP

7、4,v 4v7,v7,v8,v( d3v 6963v 448v v9) ) v8,v(vv9,49v8 v v9 vv9 v( d( d( dvv 7878v) vv 7979v) vv 8989以 v4、v7、v8、v9 为顶点，它们之间的距离为边权构造完备图 G1求出 G1 的最小权完美匹配 M=(v4,v7(),v8,v9)在 G 中沿 v4 到 v7 的最短路径添加重复边，沿 v8 到 v9 的最短路径 v8v9 添图 G2G2 中一条欧拉巡回就是 G 的一条最佳巡回其加重复边，得权值为图定义 设 G=(V,E)是连通无向图（）经过 G 的每个顶点正好一次的路径，称为 G 的一条路径（

8、）经过 G 的每个顶点正好一次的圈，称为 G 的哈密尔顿圈或 H 圈（）含 H 圈的图称为图或 H 图问题-定义需要某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是问题若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是问题就成为在图中寻找一条经过每个顶点至少一次的最短闭通路问题图G=(V,E)中，定义在（）权最小的圈称为最佳H圈（）经过每个顶点至少一次的权最小的闭通路称为最佳回路一般说来，最佳路，同样最佳圈不一定是最佳回路也不一定是最佳回圈H回路，长22回路，长4最佳图G=(V,E)中，若对任意 x,y,zV，z x,z y,都定理在有 w(x,y) w(x,z)+w(z,y)，则图 G 的最佳 H 圈也是最佳回路回路问题可转化为最佳 H 圈问题方法是由给最佳定的图 G=(V,E)构造一个以V为顶点集的完备图 G=(V,E)，E的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权即： x,y E,w(x,y)=mindG(x,y)图 G 的最佳回路的权与 G的最佳 H 圈的权相同定理问题近似算法：二边逐次修（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1：（）对所有的 i ,j，1i+1jn,若w(vi, vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则在 C0 中删去边(vi