资源描述：
《第九章行遍性问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第九章行遍性问题一、中国邮递员问题(-)欧拉图定义1设G二(V,E)是连通无向图(1)经过G的每边至少一次的闭通路称为巡回.(2)经过G的每边正好一次的巡回称为欧拉巡回.(3)存在欧拉巡回的图称为欧拉图.对于非空连通图G,下列命题等价:欧拉道路:vlelv2e2v3e5vle4v4e3v3巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1定理1仃)G是欧拉图.欧拉巡回：vlelv2e2v3e5v1e4v4e3v3e6v1(2)G无奇次顶点.(3)G的边集能划分为圈.欧拉图非欧拉图推论1设G是非
2、平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点.(二)中国邮递员问题邮递员发送邮件时，要从邮局出发,经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线.这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图.中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回・这样的巡回称为最佳巡回.算法1、G是欧拉图此时G的任何一个欧拉巡回便是最佳巡回•问题归结为在欧拉图屮确定一个
3、欧拉巡回.Fleury算法：求欧拉图的欧拉巡回Fleury算法■基本思想：从任一点出发，每当访问一条边时，先要进行检查.如果可供访问的边不只一条，则应选一条不是未访问的边集的导岀子图的割边作为访问边，直到没有边可选择为止.Fleury算法一算法步骤：(1)任选一个顶点V0,令道路wo=vo⑵假定道路昭二 1'"2…Wi已经选好，则从E{ci，c2,•:屮选一条边"
4、进行时就停止.2、G不是欧拉图若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次.解决这类问题的一般方法是，在一些点对之间引入重复边(重复边与它平行的边具有相同的权)，使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小.情形1G正好有两个奇次顶点(1)用Dijkstra算法求出奇次顶点"与卩之间的最短路径P・(2)令G*二GuP,则G*为欧拉图.(3)用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回.情形2G有2n个奇次顶点(n>2)Edmonds最小对集算法：基木思想：先将奇次顶
5、点配对，要求最佳配对，即点对之间距离总和最小.再沿点对之间的最短路径添加重复边得欧拉图G*,G*的欧拉巡冋便是原图的最佳巡冋.算法步骤：(1)fflFloyd算法求出的所有奇次顶点之间的最短路径和距离.(2)以G的所有奇次顶点为顶点集(个数为偶数)，作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G]・(3)求IBG1的最小权理想兀配M,得到奇次顶点的最佳配对.(4)在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*.(5)用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回
6、.例求右图所示投递区的一条最佳邮递路线.1.图中有孑八乃、心、内四个奇次顶点用Floyd算法求出它们Z间的最短路径和距离:%=v4v3v2v7,J（v4,v7）=5©，8二即（比心）=3^4v9=v4v8v9,rf（v4v9）=6仏*二叽,〃（吟也）=9^•7v9=v7v9^（v7，v9）=6〈厂唧9，〃（％*9）=32.以…炽以、内为顶点，它们之间的距离为边权构造完备图G}.3.求出G的最小权完美匹配r7),(v8frP)}4.在G中沿巾到乃的最短路径添加重复边，沿w到内的最短路径层内添加重复边,得
7、欧拉图b・G?中一条欧拉巡回就是G的一条最佳巡回.其权值为64.二、推销员问题(―)哈密尔顿图定义设G=(V,E)是连通无向图(1)经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径.(2)经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或II圈.(二)推销员问题流动推销员需要访问某地区的所有城镇，最后冋到出发点•问如何安排旅行路线使总行程最小.这就是推销员问题.若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离(或时间、费用)，于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的
8、最短闭通路问题.定义在加权图G二(V,E)中，(1)权最小的哈密尔顿圈称为最佳H圈.(2)经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路.一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈.H冋路，反22最佳推销员冋路，反4Vj定理1在加权图G二(V,E)中，若对任意K,z丰x,z丰y,都有W(x,y)
