第9讲 行遍性问题

行遍性问题数学建模与数学实验行遍性问题一、中国邮递员问题二、推销员问题三、建模案例：最佳灾情巡视路线（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题定义设图G=（V，E），ME，若M的边互不相邻，则称M是G的一个匹配.若顶点v与M的一条边关联，则称v是M饱和的.设M是G的一个匹配，若G的每个顶点都是M饱和的，则称M是G的理想匹配.7312341245566789割边G的边是割边的充要条件是不含在G的圈中．割边的定义：设G连通，E(G),若从G中删除边后，图G-{}不连通，则称边为图G的割边．eeeeeevvvvvvveeeeeeeeee3v1v2v3v4e1e2e4e5e6欧拉图定义１设G=(V,E)是连通无向图（１）经过G的每边至少一次的闭通路称为巡回．（２）经过G的每边正好一次的巡回称为欧拉巡回．（３）存在欧拉巡回的图称为欧拉图．（４）经过G的每边正好一次的道路称为欧拉道路．e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定理１对于非空连通图G，下列命题等价：（１）G是欧拉图．（２）G无奇次顶点．（３）G的边集能划分为圈．推论１设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点．e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图返回中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为最佳巡回．中国邮递员问题-算法1.G是欧拉图此时G的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回．Fleury算法：求欧拉图的欧拉巡回.Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.v7e3v1v2v3v4e1e2e4e5v5e6e6e7e8e9e10Fleury算法—算法步骤：（１）任选一个顶点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不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．情形１G正好有两个奇次顶点（１）用Dijkstra算法求出奇次顶点u与v之间的最短路径P．（２）令G*=GP，则G*为欧拉图.（３）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9情形２G有２n个奇次顶点（n２）Edmonds最小对集算法：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回．算法步骤：（１）用Floyd算法求出所有奇次顶点之间的最短路径和距离．（２）以G的所有奇次顶点为顶点集（偶数个元素），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1．（４）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*．（５）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．例　求右图所示投递区的一条最佳邮递路线．1．图中有v4、v7、v8、v9四个奇次顶点用Floyd算法求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2．以v4、v7、v8、v9为顶点，他们之间的距离为边权构造完备图G1．3．求出G1的最小权完美匹配M={(v4,,v7),(v8,v9)}.4．在G中沿v4到v7的最短路径添加重复边，沿v8到v9的最短路径v8v9添加重复边，得欧拉图G2．G2中一条欧拉巡回就是G的一条最佳巡回．其权值为64．返回哈密尔顿图定义设G=(V,E)是连通无向图.（１）经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径．（２）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈．（３）含H圈的图称为哈密尔顿图或H图．返回推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4定理１在加权图G=(V,E)中，若对任意x,y,zV，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圈的权相同．推销员问题近似算法：二边逐次修正法：(1)任取初始H圈:C0=v1,v2,…,vi,,…,vj,…,vn,v1(2)对所有的i,j，1i+1jn,若w(vi,vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则在C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi,vj)和(vi+1,vj+1)，形成新的H圈C，即C=v1,v2,…,vi,,vj,vj-1,…,vi+1,vj+1,…,vn,v1(3)对C重复步骤(2)，直到条件不满足为止，最后得到的C即为所求．例对以下完备图，用二边逐次修正法求较优H圈．返回