中国邮递员问题欧拉巡回.ppt

1、基本概念与基本结论,主要内容,求欧拉图欧拉巡回的算法,原始模型,求解中国邮递员问题的算法,案例：铲雪车的行驶路线问题,原始模型,问题：一位邮递员从邮局选好邮件去投递，他必须经过他所管辖的每条街至少一次，然后回到邮局，如何选择一条总行程最短的路线？,基本概念与基本结论,设G=(V,E)是连通无向图。 1）巡回：经过G的每边至少一次的封闭路线。 2）欧拉巡回：经过G的每边正好一次的巡回。 3）欧拉图：存在欧拉巡回的图。 4）欧拉道路：经过G的每边正好一次的道路。 5）最佳巡回：加权连通图的边权总和最小的巡回。,无向图的情形,基本概念与基本结论,结论一：连通图G是欧拉图的充要条件是G无奇次顶点。 结

2、论二：连通图G有欧拉道路的充要条件是G最多有两个奇次顶点。 结论三：任何无向图的奇次顶点数目必为偶数。,无向图的情形,基本概念与基本结论,设G=(V,E)是弱连通有向图。 1）有向巡回：经过G的每条弧至少一次的有向封闭路线。 2）有向欧拉巡回：经过G的每条弧正好一次的有向巡回。 3）有向欧拉图：存在有向欧拉巡回的有向图。 4）有向欧拉道路：经过G的每条弧正好一次的有向道路。 5）最佳有向巡回：加权连通有向图的边权总和最小的有向巡回。,有向图的情形,基本概念与基本结论,结论一：弱连通有向图D是有向欧拉图的充要条件是D的任何奇次顶点的出次等于入次。 结论二：弱连通有向图D有以u为起点，v为终点的有

3、向欧拉道路的充要条件是：u的出次比入次多1， v的出次比入次少1， 其余顶点的出次等于入次。,有向图的情形,Fleury算法 设G是欧拉图。 V(G) = v0,v1,vn , E(G) = e1,e2,em 1) 任选顶点为v0 ，置途径W= v0 。 2) 设途径W= v0 e1v1 ei vi已经选定，则按下述条件 从E - e1,e2, ei中选取ei+1。 （a） ei+1与vi相关联。 （b） 除非没有别的选择，否则一定要使ei+1不是 G - e1,e2, ei的割边。 3 ) 当第2步不能执行时，算法停止。 停止后，W 即是所求欧拉回路。,求欧拉图欧拉巡回的算法,Hierhol

4、zer算法 设G是欧拉图。 1) 任选顶点为v0 ，以 v0为 起点，生成一个闭道路T0, i0； 2) 在Ti上选择一个顶点vi，要求vi有不在Ti上的关联边；在图G-E(Ti)中构造以vi为起点的闭道路T,将T插入到Ti的顶点vi处，形成一个更长的闭道路Ti+1=TiT； 3 ) 若E(Ti+1)=E(G), 则停止；否则i i+1, 返回2)。 停止后， Ti+1 即是所求欧拉回路。,求欧拉图欧拉巡回的算法,Hierholzer算法也适合于有向欧拉图，只要将其中的闭道路改为有向闭道路即可。,求欧拉图欧拉巡回的算法,一般解法 设G是连通加权图。 1) 对G添加重复边，使G成为欧拉图G*,

5、且要求添加的重复边权和近可能小； 2) 在G*中求一条欧拉巡回。 走两条重复边相当于原图的边走两遍。 结论：若连通图G正好有两个奇次顶点u,v，沿u到v的一条最短路径添加重复边得到欧拉图G*, 则G*的欧拉巡回便是G的最佳巡回。,求解中国邮递员问题的算法,最小权对集法（Edmonds) 设G是连通加权图。 1) 求G的所有奇次顶点之间的最短路径及其长度； 2) 以G的所有奇次顶点为顶点集作一完全图，各条边上的权赋为两端点在原图中的最短路径长度，得到一个加权完全图，记为G1；求G1的最小权理想匹配M, 得到奇次顶点的最佳配对； 3）在G中，沿最佳配对奇次顶点间的最短路径添加重复边得欧拉图G*，G

6、*的欧拉巡回即为所求。,求解中国邮递员问题的算法,问题 某地区的双车道公路如图1的图G（单位是千米），路上积满了雪 。一辆扫雪车从v1点出发，扫除公路上的所有积雪，最后回到v1 。 要求1） 请你为扫雪车选择一条路径，使它经过的总路程最短。 要求2） 现在先进的喷气扫雪车只需沿公路一侧行驶，就能清除两个车道的积雪。如果改用喷气扫雪车来扫雪，再请你为它选择一条路径，使它经过的总路程最短。,案例1：双车道公路扫雪模型,案例1：双车道公路扫雪模型,要求1）的解法1 由于是双车道，因此可将每条边看成来回两条异向弧，此时，图是有向欧拉图，可用hierholzer算法在有向图上求出有向欧拉巡回。,案例1：

7、双车道公路扫雪模型 hierholzer算法求解,要求1）的解法2 还可用深度优先搜索法（迷宫法则），遍历所有边，且每边正好来回各走一次。 迷宫任务：从迷宫入口处出发，每个走廊都要搜索，最后再从入口出来,案例1：双车道公路扫雪模型 深度优先搜索法遍历求解,要求1）的解法2（续） 迷宫法则： 1）沿着未走过的通道尽可能远地走下去，走到死胡 同或那里已无末走过的走廊可选时，沿原路返回； 2）到达路口，若有未走过的走廊时，沿这一走廊尽 可能远地走下去，最后即可按索退全部走廊 和厅室，再由入口处出迷宫,案例1：双车道公路扫雪模型 深度优先搜索法遍历求解,威廉王迷宫,案例1：双车道公路扫雪模型 深度优先

8、搜索法遍历求解,要求1）的解法2（续） 扫雪车行驶规则： 从起点出发，优先选择未作业过的路段； 到达交差路口时，若身后路面的两个车道都已铲且前面还有未作业过的路段，或前方路段都未作业过，则驶入最靠右边的路段继续作业；否则，身后路面只铲了一个车道，应掉头铲另一个车道。 3. 行驶到一头不通的道路尽头应掉头，在反向车 道上作业。,案例1：双车道公路扫雪模型 深度优先搜索法遍历求解,案例1：双车道公路扫雪模型 深度优先搜索法遍历求解,铲雪车的行驶路线问题（MCM 90B题） 下页 地图中实线表示马里兰州(Maryland)咸克米克市(w5comico)清除积雪区域的双车道道路，虚线是州高速公路。雪后，两辆扫雪车从地图*