第十九章 行遍性问题.doc

《第十九章 行遍性问题.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、法便解决了这一问题.Fleury算法的基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.注：割边的定义：设G联通，，若从G中删除边e后，图G-{e}不联通，则称边e为图G的割边.Fleury算法：求欧拉图的欧拉巡回：（１）任选一个顶点，令道路.（２）假定道路已经选好，则从中选一条边，使：a）与相关联b）除非不能选择，否则一定要使不是的割边．（３）第（２）步不能进行时就停止．2.G不是欧拉图若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．

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

5、*的欧拉巡回便是原图的最佳巡回．算法步骤：（１）用Floyd算法求出的所有奇次顶点之间的最短路径和距离．（２）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1．（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．（４）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*．（５）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．例　求图19-1所示投递区的一条最佳邮递路线．图19-1解图中有v4、v7、v8、v9四个奇次顶点，用Floyd算法求出它们之间的最短路径和距离：以v

6、4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图G1，如图19-2.图19-2图19-3求出G1的最小权完美匹配M={(v4,,v7),(v8,v9)}.在G中沿v4到v7的最短路径添加重复边，沿v8到v9的最短路径v8v9添加重复边，得欧拉图G2．如图19-3.G2中一条欧拉巡回就是G的一条最佳巡回．其权值为64．二、推销员问题一个旅行售货员想去访问若干城镇，然后回到出发地.给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？它可归结为这样的图论问题：在一个赋权完全图中,找出一个最小权的H圈,称这种圈为

7、最优圈.但这个问题是NP-hard问题，即不存在多项式时间算法.也就是说,对于大型网络(赋权图),目前还没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解.1、哈密尔顿图定义1　设G=(V,E)是连通无向图（1）经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径，简称H路径.（2）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈.（3）含H圈的图称为哈密尔顿图或H图．2、推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题若用顶点表示城镇，边表示连

8、接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个