文档介绍：第十九章行遍性问题
一、中国邮递员问题
定义1 设G=(V,E)是连通无向图
(1)经过G的每边至少一次的闭通路称为巡回.
(2)经过G的每边正好一次的巡回称为欧拉巡回.
(3)存在欧拉巡回的图称为欧拉图.
(4)
v1
v2
v3
v4
e1
e2
e4
e5
e3
v1
v2
v3
v4
e1
e2
e4
e5
e6
e3
欧拉道路: 欧拉巡回:
巡回:
定理1 对于非空连通图G,下列命题等价:
(1)G是欧拉图.
(2)G无奇次顶点.
(3)G的边集能划分为圈.
v1
v1
v2
v3
v4
e1
e2
e4
e5
e3
e3
v1
v2
v3
v4
e1
e2
e4
e5
e6
欧拉图非欧拉图
推论1 设G是非平凡连通图,则G有欧拉道路的充要条件是G最多只有两个奇次顶点.
. 中国邮递员问题
邮递员发送邮件时,要从邮局出发,经过他投递范围内的每条街道至少一次,然后返回邮局,.
若将投递区的街道用边表示,街道的长度用边权表示,邮局街道交叉口用点表示,:在一个非负加权连通图中,.
1. G是欧拉图
.
Fleury算法的基本思想:从任一点出发,每当访问一条边时,,则应选一条不是未访问的边集的导出子图的割边作为访问边,直到没有边可选择为止.
注:割边的定义:设G联通,,若从G中删除边e后,图G-{e}不联通,则称边e为图G的割边.
Fleury算法:求欧拉图的欧拉巡回:
(1)任选一个顶点,令道路.
(2)假定道路已经选好,则从中选一条边,使:
a)与相关联
b)除非不能选择,否则一定要使不是的割边.
(3)第(2)步不能进行时就停止.
2. G不是欧拉图
若G不是欧拉图,,在一些点对之间引入重复边(重复边与它平行的边具有相同的权),使原图成为欧拉图,但希望所有添加的重复边的权的总和为最小.
情形1 G正好有两个奇次顶点
设G正好有两个奇次顶点u和v,求G 的最佳巡回如下:
(1) 用Dijkstra算法求出奇次顶点u与v之间的最短路径P
(2)令G*=GP,则G*为欧拉图
(3)用Fleury算法求出G*的欧拉巡回,这就是G的最佳巡回.
情形2 G有2n个奇次顶点(n2)
Edmonds最小对集算法:
基本思想:
先将奇次顶点配对,要求最佳配对,*,G*的欧拉巡回便是原图的最佳巡回.
算法步骤:
(1)用Floyd算法求出的所有奇次顶点之间的最短路径和距离.
(2)以G的所有奇次顶点为顶点集(个数为偶数),作一完备图,边上的权为两端点在原图G中的最短距离,将此完备加权图记为G1.
(3)求出G1的最小权理想匹配M,得到奇次顶点的最佳配对.
(4)在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*.
(5)用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添加重复边,-3.
.
二、推销员问题
一个旅行售货员想去访问若干城镇,,应怎样计划他的旅行路线,使他能对每个城镇恰好经过一次而总距离最小?
它可归结为这样的图论问题:在一个赋权完全图中,找出一个最小权的H圈,称这种圈为最优圈.
但这个问题是NP-hard问题,,对于大型网络(赋权图),目前还没有一个求解旅行售货员问题的有效算法,因此只能找一种求出相当好(不一定最优)的解.
1、哈密尔顿图
定义1 设G=(V,E)是连通无向