第九章 行遍性问题.docVIP

行遍性问题 中国邮递员问题 欧拉图 定义１　设G=(V,E)是连通无向图 (1)经过G的每边至少一次的闭通路称为巡回． (2)经过G的每边正好一次的巡回称为欧拉巡回． (3)存在欧拉巡回的图称为欧拉图． (4)经过G的每边正好一次的道路称为欧拉道路． 欧拉道路：v1e1v2e2v3e5v1e4v4e3v3 巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1 (3)G的边集能划分为圈． 推论1　设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点． (二)中国邮递员问题 算法 Fleury算法：求欧拉图的欧拉巡回 Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止. 2、G不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次． 解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小． G正好有两个奇次顶点 用Dijkstra算法求出奇次顶点u与v之间的最短路径P． (2)令G*=GP，则G*为欧拉图． (3)用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回． 情形2　G有2n个奇次顶点（n２） Edmonds最小对集算法： 基本思想： 先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回． 算法步骤： (1)用Floyd算法求出的所有奇次顶点之间的最短路径和距离． (2)以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1． (3)求出G1的最小权理想匹配M，得到奇次顶点的最佳配对． (5)用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回． 例　求右图所示投递区的一条最佳邮递路线． 1．图中有v4、v7、v8、v9四个奇次顶点 用Floyd算法求出它们之间的最短路径和距离： 2．以v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图G1． 3．求出G1的最小权完美匹配M={(v4,,v7),(v8,v9)} 4．在G中沿v4到v7的最短路径添加重复边，沿v8到v9的最短路径v8v9添加重复边，得欧拉图G2．G2中一条欧拉巡回就是G的一条最佳巡回．其权值为64． 二、推销员问题 哈密尔顿图 (3)含H圈的图称为哈密尔顿图或H图． 推销员问题 流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题． 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题． 定义　在加权图G=(V,E)中， 权最小的哈密尔顿圈称为最佳H圈． 经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路． 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈． C重复步骤(2)，直到条件不满足为止，最后得到的C即为所求． 例　对以下完备图，用二边逐次修正法求较优H圈． 三、建模案例：最佳灾情巡视路线 e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 e3 v1 v2 v3 v4 e1 e2 e4 e5 e3 v1 v2 v3 v4 e1 e2 e4 e5 e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 欧拉图 非欧拉图 V7 e3 v1 v2 v3 v4 e1 e2 e4 e5 V5 V6 e6 e7 e8 e9 e10 V7 e3 v1 v2 v3 v4 e1 e2 e4 e5 V5 V6 e6 e7 e8 e9 H回路，长22 最佳推销员回路，长4