行遍性问题.ppt

1、行遍性问题,安徽工业大学数理学院,行遍性问题,一、中国邮递员问题,二、推销员问题,1、欧拉图,2、中国邮递员问题,1、哈密尔顿图,2、旅行商问题,欧拉图,18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥。将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题这就是哥尼斯堡七桥问题，一个著名的图论问题。,1727年20岁瑞士数学家欧拉，被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究。他的德国朋友告诉了他这个曾经令许多

2、人困惑的问题。,1736年欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”,欧拉巧妙地把哥尼斯堡城图化为下图所示图G，他把陆地设为图G中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图G中从某一结点出发找出一条路，它通过每条边恰好一次后回到原出发结点，亦即等价于在图G中寻找一个圈，它通过G中每一条边恰好一次。,欧拉图,巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1,欧拉道路：v1e1v2e2v3e5v1e4v4e3v3,欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1,定义1: 设G=(V,E)是连通无向图,1、经过G的

3、每边至少一次的闭通路称为巡回,2、经过G的每边正好一次的巡回称为欧拉巡回(圈),3、存在欧拉巡回的图称为欧拉图,4、经过G的每边正好一次的道路称为欧拉道路,欧拉图,非欧拉图,定理1: 对于非空连通图G，下列命题等价：,1、G是欧拉图,2、G无奇次顶点,3、G的边集能划分为圈,推论1: 设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点,中国邮递员问题-定义,邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中国邮递员问题.,若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递

4、区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最佳巡回,定义: 设图G =(V，E)，ME，若M的边互不相邻，则称M是G 的一个匹配.,若顶点v与M的一条边关联，则称v是M饱和的,设M是G的一个匹配，若G的每个顶点都是M饱和的，则称M是G的理想匹配.,G的边e是割边的充要条件是e不含在G的圈中,设G连通，eE(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边,割边的定义：,割边,中国邮递员问题-算法,1、G是欧拉图,此时G的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回,Fleury算法：求欧拉图的欧拉巡

5、回,Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不止一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.,b) 除非不能选择，否则一定要使ei+1不是Gi=GE-e1,e2, ,ei 的割边,Fleury算法算法步骤：,1、任选一个顶点v0，令道路w0=v0,2、假定道路wi=v0e1v1e2eivi已经选好，则从Ee1,e2, ,ei中选一条边ei+1，使：,a) ei+1与vi相关联,3、第2步不能进行时就停止,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在一些点对之间引入重复

6、边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小,2、G不是欧拉图,情形G正好有两个奇次顶点,1、用Dijkstra算法求出奇次顶点u与v之间的最短路径P,2、令G*=GP，则G*为欧拉图,3、用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回,情形2G有2n个奇次顶点（n2）,Edmonds最小对集算法：,基本思想：,先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回,算法步骤：,1、用Floyd算法求出的所有奇次顶点之间的最短路径和距离,2、以G的所有奇次顶

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

8、沿v8到v9的最短路径v8v9添加重复边，得欧拉图G2G2中一条欧拉巡回就是G的一条最佳巡回其权值为64,与欧拉圈非常类似的问题是哈密尔顿圈的问题。1859年，爱尔兰数学家哈密尔顿(W.R.Hamilton)首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市，这个正十二面体同构于一个平面图，要求旅游者能否找到沿着正十二面体的棱，从某个顶点(城市)出发，经过每个顶点(城市)恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。,哈密尔顿图,哈密尔顿图,定义: 设G=(V,E)是连通无向图,1、经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径,2、经过G的每个顶

9、点正好一次的圈，称为G的哈密尔顿圈或H圈,3、含H圈的图称为哈密尔顿图或H图,按图中所给的编号进行旅游，便是哈密尔顿问题的解。,对于任何连通图也有类似的问题。,哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一,最小Hamilton回路与旅行商问题,设G=(V,E,w)，其中V是顶点集，E是边集，w为定义在E上的权（非负）。,G的一个Hamilton回路是顶点集V上的一个循环排列p=v1v2vnvn+1(v1=vn+1)，其中vivi+1E，w(p)定义为p上所有边权之和，当w(p)达到最小时，p称为最

10、小Hamilton回路。,G的一个旅行商路线是顶点集V的可重复的但不遗漏的一个循环排列，多旅行商路线则是顶点集可重复的但总体上不遗漏的多个循环排列。,Hamilton回路（圈）,旅行商线路,若G是连通的但不是完全图时，G可能不存在Hamilton回路，更不存在最小Hamilton回路，但若G是连通的，就一定存在最优旅行商路线。,右图不存在Hamilton回路，但最优旅行商线路为v1v2 v4 v5 v4 v3 v1,若G完全图时，则G一定存在Hamilton回路，且亦存在最小Hamilton回路，但该最小Hamilton回路未必就是最优旅行商路线。,试考察右图,右图的最小Hamilton回路为

11、： v1 v2 v3 v4 v5v1,右图的最优旅行商路线为： v1 v2 v3 v4 v1 v5v1,最小Hamilton回路长19，最优旅行商路线长17。,问题：在什么条件下，最小Hamilton回路就是最优旅行商线路？,定理,若完全图G=(V,E,w)的权满足三角不等式,则G的最小Hamilton回路就是最优旅行商路线,最优旅行商路线无法直接求，要设法将其化为求最小Hamilton回路，由上面的结论，设法将图化为完全图且边权满足三角不等式。,方法如下（若G是非完全图）,1）将G=(V,E,w)化为完全图G=(V,E,w)，其中wij用vi到vj的最短路代替，这样G的边权就满足了三角不等式

12、。,2）求G的最小Hamilton回路。,3）将求出的最小Hamilton回路中的边vivj用相应的vi到vj的最短路代回，即求出了最优旅行商路线。,问题转化为如何求Hamilton圈问题。,求Hamilton圈为一难解问题，现已从理论上证明了其无有效算法。所以仅能求近似解。,一种近似算法（改良圈法）,1）在完全图上任取一Hamilton圈，不妨设为C=v1v2vnv1,2）检查是否存在ij，使vi-1vjE(G), vivj+1E(G)且成立wi,j+1+wi-1,jwi-1,i+wj,j+1,若成立则有改良圈C1=v1v2vi-1vjvj-1 vivj+1vj+2 vnv1。,3）令C=C1，转2），直到停止。,该算法得到的Hamilton圈未必是理想圈，但其算法复杂度低。,示例,从北京(Pe)到伦敦(L)、墨西哥城(MC)、纽约(NY)、巴黎(Pa)、东京(T)各城去环球讲学，乘飞机到各城一次再返回首都北京，应如何安排行程最省旅费？（各城间距离作为边权在图中标出）,问题求解,给出初始圈 C=(Pe) (T) (L) (MC) (NY) (Pa) (Pe),L,得到改良圈,C=(Pe) (T) (MC) (NY) (L) (Pa) (Pe),其总长度为13+70+21+35+2+51=192,该结论未必达到最小Ham