第三章行遍性问题资料.ppt

第三章 行遍性问题 3.1 中国邮路问题 3.1.1 欧拉图 定义:一个图G=(V,E)中存在的一条通过各边一次且仅一次的回路(起点和重点重合的通路),称为欧拉回路;具有欧拉回路的图称为欧拉图.(又称为欧拉环游或欧拉巡回) 图G=(V,E)中的一条通过各边一次并且仅一次的道路称为欧拉道路.具有欧拉道路的图称为半欧拉图. 注:欧拉图一定是半欧拉图,反之不一定. 例如: 定理1:非空连通图G是欧拉图的充分必要条件是G中每个顶点的次数为偶数. 推论1:非空连通图G是半欧拉图的充分必要条件是G中至多两个顶点的次数为奇数. 定理2:非空连通图G是欧拉图的充分必要条件是G可以表示成没有公共边的若干个圈的并. 3.1.2 中国邮递员问题 邮递员的工作是在邮局里选出邮件然后再返回邮局.自然,他必须走过他投递范围内的每一条街道至少一次.在这个前提下,希望选择一条尽可能短的路线.这个问题名为中国邮递员问题,因为它首先是中国数学家管梅谷(1962年)研究的. 在一个赋权图中,环游v0e1v1en…v0的权定 义为 ,显然,中国邮递员问题就是在具有非 负权的赋权连通图中找出一条最小权的环游.这种环游称为最优环游. 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的最优环游. 情形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*. 例如: 由于G中v4,v7,v8,v9是奇次顶点,v4与v7,v8与v9配对; 下面进行圈校正: 再次进行圈校正: 例如: 1.v与l配对,x与m配对,任选路径加重边: 2.成对去掉重边对于一条的: 3.进行第一次圈校正: 4.进行第二次圈校正: 3.2 推销员问题 3.2.1 Hamilton图 定义1:设G=(V,E)是连通无向图,G中的一条经过每个顶点一次并且仅一次的圈称为G的Hamilton圈,简称为H圈;具有H圈的图称为Hamilton图,简称为H图.