第十九章 行遍性问题

第十九章行遍性问题、中国邮递员问题定义1设G=(V,E)是连通无向图经过G的每边至少一次的闭通路称为巡回.经过G的每边正好一次的巡回称为欧拉巡回.存在欧拉巡回的图称为欧拉图.欧拉道路:vevevevevev11223514433欧拉巡回：vevevevevevev1122351443361欧拉道路:vevevevevev11223514433巡回：vevevevevevev1122351443351定理1对于非空连通图G,下列命题等价:G是欧拉图.G无奇次顶点.G的边集能划分为圈.

非欧拉图非欧拉图推论1设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点.19.1.2.中国邮递员问题邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线.这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图.中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回.这样的巡回称为最佳巡回.G是欧拉图此时G的任何一个欧拉巡回便是最佳巡回.问题归结为在欧拉图中确定一个欧拉巡回.Fleury算法便解决了这一问题.Fleury算法的基本思想：从任一点出发，每当访问一条边时，先要进行检查.如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.注：割边的定义：设G联通，egE(G)，若从G中删除边e后，图G-{e}不联通，则称边e为图G的割边.Fleury算法：求欧拉图的欧拉巡回：任选一个顶点y0，令道路气=V。.假定道路w=veve…ev已经选好，则从E\{e,e,…,e}中选一条边e，、/I/、-—I•]]2•,'，-~1~、-//V/°,/JI，、-、，'-.|]/使：匕+i与七相关联除非不能选择，否则一定要使。「不是G=G[E-{e,e,…,e}]的割边.i+1i12i(3)第(2)步不能进行时就停止.G不是欧拉图若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次.解决这类问题的一般方法是，在一些点对之间引入重复边(重复边与它平行的边具有相同的权)，使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小.情形1G正好有两个奇次顶点设G正好有两个奇次顶点u和v,求G的最佳巡回如下：用Dijkstra算法求出奇次顶点u与v之间的最短路径P令G*=GuP，则G*为欧拉图用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回.情形2G有2n个奇次顶点(n>2)Edmonds最小对集算法：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小.再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回.算法步骤：用Floyd算法求出的所有奇次顶点之间的最短路径和距离.以G的所有奇次顶点为顶点集(个数为偶数)，作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1.求出G1的最小权理想匹配M，得到奇次顶点的最佳配对.在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*.用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回.例求图19-1所示投递区的一条最佳邮递路线.V610V3图19-1

解图中有v4、v7、v8、v9四个奇次顶点，用Floyd算法求出它们之间的最短路径和距离：P=VVVV,d(v,v)=5V/7432747P=VV,d(v,v)=3V4V84848P=VVV,d(vv)=6V4V94894,9P=VV,d(v,v)=9V7V87878P=VV,d(v,v)=6V7V97979P=VV,d(v,v)=3V8V98989以v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图勺，如图19-2.图19-3图图19-3求出G的最小权完美匹配M={(v,v),(v,v)}.14,789在G中沿v到匕的最短路径添加重复边，沿v到vq的最短路径vv添加重复边，得欧4/8989拉图G2.如图19-3.G2中一条欧拉巡回就是G的一条最佳巡回.其权值为64.二、推销员问题一个旅行售货员想去访问若干城镇，然后回到出发地.给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？它可归结为这样的图论问题：在一个赋权完全图中，找出一个最小权的H圈，称这种圈为最优圈.但这个问题是NP-hard问题，即不存在多项式时间算法也就是说,对于大型网络(赋权图),目前还没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好(不一定最优)的解.1、哈密尔顿图定义1设G=(V,E)是连通无向图经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径，简称H路径.经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈.含H圈的图称为哈密尔顿图或H图.2、推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点.问如何安排旅行路线使总行程最小.这就是推销员问题若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离(或时间、费用)，于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义2在加权图G=(V,E)中，(1)权最小的哈密尔顿圈称为最佳H圈.经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路.一般说来，最佳哈密尔顿圈不一定是最佳推销员回路同样最佳推销员回路也不一定是一般说来，最佳哈密尔顿圈不一定是最佳推销员回路同样最佳推销员回路也不一定是最佳哈密尔顿圈.定理1在加权图G=(V,E)中，若对任意x,y,zeV，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在图中最短路的权.即：Vx,yeE',w(x,y)=min@(x,y)

定理2加权图G的最佳推销员回路的权与G’的最佳H圈的权相同.3、推销员问题近似算法推销员问题近似算法：二边逐次修正法任取初始H圈：C=vv...vv12n1对所有的i,j,1<i+1<j<v，若w(vv)+w(vv)<w(vv)+w(vv)iji+1j+1ii+1jj+1则在％中删去边vv和vv而加入边vv和vv，形成新的H圈C,即0ii+1jj+1iji+1j+1C=vv...vvv12ijj+1见图19-4图19-4...vvv...vvi+1j+1j+2n见图19-4图19-4...vvv...vvi+1j+1j+2n1图19-5例1解首先任选一初始H圈：C=vvvvvvv01234561见图19-6（a）.可以看出，w(vv)+wv.珊J去边vv和vv,加入边vv,vv,得到一个新451245142w(vv)+C=vvvvvvv11432561而图19-6(b)中，w(vv)+w(vv)<w(vv)+w(vv),删去边vv和vv,加入边vv,TOC\o"1-5"\h\z15261625162515v2七’得到一个新的H圈C2，见图19-6(C).而图(C)中，w(vv)+w(vv)<w(vv)+w(vv)，删去边vv和vv，加入边vv,vv，得到一个1345153415341345新的H圈C,C=vvvvvvv，见图19-6(d).其权为W(C)=192.3314562313©⑷图19-6©⑷为了知道找出的这个解的好坏可用最优H圈的权的下界与其比较而得出.即利用最小生成树可得最优H圈的一个下界，方法如下：设C是G的一个最优H圈，则对G的任一顶点v,C-v是G-v的路，也G-v是的生成树.如果T是G-v的最小生成树，且匕是气与v关联的边中权最小的两条边，则w(T)+w(e)+w(e2)将是w(C)的一个下界.若取v=v3，得G-v3的一最小生成树(实线)，(图19-7)其权w(T)=122，与v3关联的权最小的两条边为vv和vv,故w(C)=w(T)+w(vv)+w(vv)=178.故最优H圈的权应13231323满足178<w(C)<192.图19-7三、最佳灾情巡视路线1998年全国大学生数学模型竞赛B题中的两个问题.一、问题今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.乡（镇）、村的公路网示意图见图19-8二、基本假设汽车在路上的速度总是一定，不会出现抛锚等现象；巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；每个小组的汽车行驶速度完全一样；分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外.三、模型的建立与分析本问题要求在某县的乡镇、村公路网中，寻找从县政府所在地图中点出发，走遍各乡镇、村，又回到县政府所在地，使总路程或时问最少将公路网图中，每个乡镇或村看为图中图19-8的一个节点，各乡镇、村之间的公路看作图中对应节点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为图论中的加权网络图，问题就转化为一个图论问题，即在给定的加权网络图中寻找从给定点出发，行遍所有顶点至少一次再回到点，使得总权路程或时间最小.算法一求加权图G(V,E)的最佳推销员回路的近似算法：1、用图论软件包求出G中任意两个顶点间的最短路，构造出完备图G'(V,E'),V(x,y)eE',«)(x,y)=Mindd(x,y)；G2、输入图G'的一个初始H圈；3、用对角线完全算法产生一个初始H圈；4、随机搜索出G'中若干个H圈，例如2000个；5、对第2、3、4步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈;6、在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解.由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果.问题一若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个推销员的最佳推销员回路问题即在加权图G中求顶点集V的划分，V,V,^V，将g分成n个生成子图g[y],g\y],・・・G[y]使得12n12n(1)顶点OeV,i=1,2,,n.i⑵Uy=y(g).ii=1Max从c)—①G)i,7Mv\JR，其中c是y的导出子图g[v]中的最佳推销员回Max®(C)iiiii路，®(C)为C的权，i,J=1,2,…，n.乙(c)=Min.ii=1定义称Max®(c)—®(c)iJ1气=—ii为该分组的实际路程均衡度.a为最大容许均衡度.显然0<a0<1,a0越小，说明分组的均衡性越好.取定一个a后，a0与a满足条件(3)的分组是一个均衡分组.条件(4)表示总巡视路程最短.此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题.我们只能去寻求一种较合理的划分准则，对图进行初步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件(3).从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为干枝，见图19-9.从图中可以看出，从O点出发到其它点共有6条干枝，它们的名称分别为①，②，③，④，③，⑥.

支上及其分枝上的点分在同一组;准则二：应将相邻的干枝上的点分在同一组;)支上及其分枝上的点分在同一组;准则二：应将相邻的干枝上的点分在同一组;),10_.0\43.227z.A/o28、22is\(7.9\12.1\/82311>7.9\/9.2113^1-clZ8准则三：尽量将长的干枝与短的干枝分在同一组.由上述分组准则，们找到两种分组形式如下分组一：（⑥，①），（②，③），（⑤，④）分组二：（①，②），（③，④），（⑤，⑥）显然分组一的方法极不均衡，故考虑分组二.对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线.在每个子图所构造的完备图中，取一个尽量包含图中树上的边的H圈作为其第2步输入的初始圈.分组二的近似解见表1表1小组名称路线总路线长度路线的总长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C241.9mO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5因为该分组的均衡度①（C）—①（C）241.9-125.5

气=Mhx^（C）=241.9ii=1,2,3所以此分法的均衡性很差.为改善均衡性，将第II组中的顶点C,2,3,D,4划归第III组，重新分组后的近似最优解见表2.小组名称路线总路线长度路线的总长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-O216.4mO-R-29-Q-30-32-31-33-35-34-A-1-B-3-D-4-D-3-2-O192.3因为该分组的均衡度①（C）-①（C）216.4—191.1a=%-『1==11.69%0Max®（c）216.4ii=1,2,3所以这种分法的均衡性较好.问题二当巡视人员在各乡镇、村的停留时问一定，汽车的行驶速度一定，要在24小时内完成巡视，至少要分几组及最佳的巡视路线.由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有了17个，村共有35个.计算出在乡镇及村的总停留时间为17x2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，故至少要分4组.由于该网络的乡镇、村分布较为均匀，故有可能找出停留时问尽量均衡的分组，当分4组时各组停留时间大约为岑=17.25小时，则每组分配在路途上的时问大约为24-17.25=6.75小时而前面讨论过，分三组时有个总路程59