第三章 行遍性问题

第三章行遍性问题3.1中国邮路问题3.1.1欧拉图定义:一个图G=(V,E)中存在的一条通过各边一次且仅一次的回路(起点和重点重合的通路),称为欧拉回路;具有欧拉回路的图称为欧拉图.(又称为欧拉环游或欧拉巡回)图G=(V,E)中的一条通过各边一次并且仅一次的道路称为欧拉道路.具有欧拉道路的图称为半欧拉图.注:欧拉图一定是半欧拉图,反之不一定.例如:Euler图半Euler图定理1:非空连通图G是欧拉图的充分必要条件是G中每个顶点的次数为偶数.推论1:非空连通图G是半欧拉图的充分必要条件是G中至多两个顶点的次数为奇数.定理2:非空连通图G是欧拉图的充分必要条件是G可以表示成没有公共边的若干个圈的并.3.1.2中国邮递员问题邮递员的工作是在邮局里选出邮件然后再返回邮局.自然,他必须走过他投递范围内的每一条街道至少一次.在这个前提下,希望选择一条尽可能短的路线.这个问题名为中国邮递员问题,因为它首先是中国数学家管梅谷(1962年)研究的.在一个赋权图中,环游v0e1v1en…v0的权定义为,显然,中国邮递员问题就是在具有非负权的赋权连通图中找出一条最小权的环游.这种环游称为最优环游.niiew1)(1.若G是欧拉图:则G的任何欧拉环游都是最优环游,因为欧拉环游是一条通过G的每条边恰好一次的环游.在这种情形下,中国邮递员问题是容易解决的,因为在欧拉图中,存在着确定欧拉环游的好算法.由弗劳瑞(Fleury)提出的算法,用依次描画一条道路的方法来构作欧拉环游,而这种描画服从一个条件:在每一步中,未描画的子图的割边仅当没有别的边可选择时才被描画.Fleury算法:(1)任取v0V(G)，令P0=v0.(2)设Pi=v0e1v1e2…eivi已经选定，按下面方法来从E(G){e1,e2,…,ei}中选取ei+1：(a)ei+1与vi相关联；(b)除非无别的边可供选择，否则ei+1不应该为Gi=G{e1,e2,…,ei}中的割边.(3)当(2)不能再进行时，算法停止.可以证明，当算法停止时所得环路(圈与圈的边不重并)Pm=v0e1v1e2…emvm（vm=v0）为G中一条欧拉环游.2.G不是欧拉图若G不是欧拉图,则G的任何一个环游经过某些边必定多于一次.解决这类问题的一般方法是在一些点对之间引入重复边(重复边与它平行的边具有相同的权),使原图成为欧拉图,但希望所有添加的重复边的权的总和为最小.情形1:G正好有两个奇次顶点.设G正好有两个奇次顶点u和v,求G的最佳环游的算法如下:(1)用Dijkstra算法求出奇次顶点u与v之间的最短路径P;(2)令G*=G∪P,则G*为欧拉图.(3)用Fleury算法求出G*的欧拉环游,这就是G的最优环游.v1v2v3v4v5v6v7v814225116812101情形2:G有2n个奇次顶点(n≥2)Edmonds于1965年提出的最小对集算法,很好的解决了这类问题.Edmonds算法的基本思想:先将奇次顶点配对,要求最佳配对,即点对之间距离和最小,再沿点对之间的最短路径添加重复边得欧拉图G*,G*的欧拉环游便是原图的最佳环游.Edmonds最小对集算法:(1)用Floyd算法求出所有奇次顶点之间的最短路径和距离;(2)以G的所有奇次顶点为顶点集(个数为偶数),作一完全图,边上的权为两端点在原图G中的最短距离,将此完全图的加权图记为G1.(3)用Edmonds算法求出最小权理想匹配M,得到奇次顶点的最佳配对.(4)在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*;(5)用Fleury算法求出G*的欧拉环游,这即为G的最优环游.注:奇偶点图上作业法:(1)把G中次数为奇数的顶点两两配对.任选G中连接每对顶点的一条道路,路上的边都添加重复边,从而得到G的赋权欧拉母图G*;(2)如果G*中关于G的某一条边添加上的重复边不只一条,则成对地删除重复边,直至最多有一条重复边为止;(3)检查G的每一个圈,如果圈上的重复边的权和大于圈的总和的一半,则进行圈校正.每校正一次得到的新的G*的圈都减少,对所有的圈进行检查并校正后得到的就是权最小的G*.例如:v1v2v3v4v5v6v7v8142251168101933v9由于G中v4,v7,v8,v9是奇次顶点,v4与v7,v8与v9配对;v1v2v3v4v5v6v7v8142251168101933v9下面进行圈校正:v1v2v3v4v5v6v7v8142251168101933v9再次进行圈校正:v1v2v3v4v5v6v7v8142251168101933v9例如:uvwxyztlkm11557226684341.v与l配对,x与m配对,任选路径加重边:uvwxyztlkm11557226684342.成对去掉重边对于一条的:uvwxyztlkm11557226684343.进行第一次圈校正:uvwxyztlkm11557226684344.进行第二次圈校正:uvwxyztlkm11557226684343.2推销员问题3.2.1Hamilton图定义1:设G=(V,E)是连通无向图,G中的一条经过每个顶点一次并且仅一次的圈称为G的Hamilton圈,简称为H圈;具有H圈的图称为Hamilton图,简称为H图.判定一个图是H图的充分必要条件至今没有解决,是一个NP-完全问题.3.2.2推销员问题流动推销员需要访问某地区的所有城镇,最后回到出发点.问如何安排旅行路线使总行程最少,这就是推销员问题.推销员问题也是NP-完全问题.若用顶点表示城镇,边表示连接两城镇的路,边上的权表示距离(或时间,费用),于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题.定义2:在加权图G=(V,E)中:(1)权最小的H圈称为最佳H圈;(2)经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路.一般说来,最佳H圈不一定是最佳推销员回路,同样,最佳推销员回路也不一定是最佳H圈.例如:下图中:唯一的H回路(v1,v2,v3,v1),其权和等于1+20+1=22,而通过点v1两次的最佳推销员回路(v1v2v1v3v1)的权和为1+1+1+1=4v1v2v31120以下定理说明何时最佳H圈也是最佳推销员回路:定理1:在加权图G=(V,E)中,若对任意x,y,z∈V(G),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在图G中的最短路的权,即:任意(x,y)∈E,w(x,y)=mindG(x,y)定理2:加权图G的最佳推销员回路的权与G的最佳H圈的权相同.因此,在加权图中寻求最佳推销员回路的问题就可转化为在一个完全加权图中寻求最佳H圈的问题,称为:TSP问题.3.2.3TSP近似算法:TSP近似算法包括构造型算法和改进型算法.构造型算法是按一定规则一次性地构造出一个解.而改进型算法则是以某一解作为初始解,逐步迭代,改进解,是一种迭代法,一般以构造型算法得到一个初始解,然后再用改进型算法逐步改进.二边逐次修正法:(1)任取初始H圈:C0=v1v2…vi…vj…vnv1(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=v1v2…vivjvj-1…vi+1vj+1…vnv1(3)对C重复步骤(2),直到条件不满足为止,最后得到的C即为所求.例:用二边逐次修正法求下图的较优H圈.v1v2v3v4v5v660562136511351612706878573568v1v2v3v4v5v6605621365113278v2v1v4v3v5v6602362178135170v1v5v6v2v3v4251137021365135v1v3v2v6v5v423521701351注:1.可以给出旅行推销员问题的解的下界的一个估计式.任选加权完全图Kp的一个顶点v,用克拉斯科(Kruskal)算法求出Kp-v的最优树T.设C是最优的(即权最小的)H圈,显然C-v也是Kp-v的一个支撑树(一个连通图G的一个连通无圈生成子图),因此:w(T)≤w(C-v)设边a和边b是Kp中与v关联的各条边之中权最小和权次小的两条边,显然有:w(T)+w(a)+w(b)≤w(C)上式给出w(C)的下界的一个估计式.2.关于最小生成树的求法.定义:T是带权图G=(V,E)的生成树（1）W(T)——T各边权之和（2）最小生成树——G的所有生成树中权最小的求最小生成树的一个算法避圈法：(Kruskal算法)设带权图G=(V,E)，(1)在G中任取一条边e1,e1不是环，st:w(e1)尽可能地小;(2)若e1,e2,…,ek已经选定,在E(G)-{e1,e2,…,ek}中选边ek+1,满足：①G[{e1,e2,…,ek,ek+1}]不含圈;②满足①的情况下，st:w(ek+1)尽可能地小(3)重复(2),直到无边可取为止.注：这种只顾当前利益的算法称为贪婪算法．例求图6所示图的一棵最小生成树.所求最小生成树为图7所示，W(T)=38.去掉顶点v5:G-v5v1v2v3v4v66056213661270685735G-v5的一棵最小生成树为下图:W(T)=60+2+35+21=118v1v2v3v4v66021235G中与v5相关联的边中权最小和次小的分别是13和51,所以118+13+51=182.较优H圈C:W(C)=35+21+70+13+51+2=192所以:182≤W(C)≤192