第十九章 行遍性问题.doc

第十九章 行遍性问题 一、中 国 邮 递 员 问 题 19.1.1. 定义１　设G=(V,E)是连通无向图 （１）经过G的每边至少一次的闭通路称为巡回． （２）经过G的每边正好一次的巡回称为欧拉巡回． （３）存在欧拉巡回的图称为欧拉图． （４）经过G的每边正好一次的道路称为欧拉道路．v1 v1 v1 v2 v3 v4 e1 e2 e4 e5 e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 e3 e3 欧拉道路： 欧拉巡回： 巡回： 定理１　对于非空连通图G，下列命题等价： （１）G是欧拉图． （２）G无奇次顶点． （３）G的边集能划分为圈． v1v1 v1 v1 v2 v3 v4 e1 e2 e4 e5 e3 e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 欧拉图 非欧拉图 推论１　设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点． 19.1.2. 邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是中国邮递员问题. 若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为最佳巡回． 1. G是欧拉图 此时G的任何一个欧拉巡回便是最佳巡回.问题归结为在欧拉图中确定一个欧拉巡回.Fleury算法便解决了这一问题. Fleury算法的基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止. 注：割边的定义：设G联通，，若从G中删除边e后，图G-{e}不联通，则称边e为图G的割边. Fleury算法：求欧拉图的欧拉巡回： （１）任选一个顶点，令道路. （２）假定道路已经选好，则从中选一条边，使： a）与相关联 b）除非不能选择，否则一定要使不是的割边． （３）第（２）步不能进行时就停止． 2. G不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小． 情形１　G正好有两个奇次顶点 设G正好有两个奇次顶点u和v,求G 的最佳巡回如下： （1） 用Dijkstra算法求出奇次顶点u与v之间的最短路径P （２）令G*=GP，则G*为欧拉图 （３）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回． 情形２　G有２n个奇次顶点（n２） Edmonds最小对集算法： 基本思想： 先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回． 算法步骤： （１）用Floyd算法求出的所有奇次顶点之间的最短路径和距离． （２）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1． （３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对． （４）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*． （５）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回． 例　求图19-1所示投递区的一条最佳邮递路线． 图19-1 解 图中有v4、v7、v8、v9四个奇次顶点，用Floyd算法求出它们之间的最短路径和距离： 以v4、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圈,称这种圈为最优圈. 但这个问题是NP-hard问题，即不存在多项式时间算法.也就是说,对于大型网络(赋权图),目前还没有一个求