第9讲-行遍性问题PPT参考课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,行 遍 性 问 题,数学建模与数学实验,1,行 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,三、建模案例：最佳灾情巡视路线,（一）欧 拉 图,（二）中 国 邮 递 员 问 题,（一）哈 密 尔 顿 图,（二）推 销 员 问 题,2,3,7,3,1,2,3,4,1,2,4,5,5,6,6,7,8,9,割边,G,的边 是割边的充要条件是 不含在,G,的圈中,割边的定义,：设,G,连通，,E,(,G,),若从,G,中删除边 后，图,G,-,不连通，则称边 为图,G,的割边,4,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧 拉 图,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,巡回：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,5,v,1,欧拉道路：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,欧拉巡回：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,6,v,1,5,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧拉图,非欧拉图,返回,6,中国邮递员问题,-,定义,7,中国邮递员问题,-,算法,Fleury,算法基本思想,：从任一点出发，每当访问,一条边时，先要进行检查如果可供访问的边不只,一条，则应选一条不是未访问的边集的导出子图的,割边,作为访问边，直到没有边可选择为止,.,8,v,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,v,5,e,6,e,6,e,7,e,8,e,9,e,10,9,若,G,不是欧拉图，则,G,的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是：在一些点对之间,引入重复边（重复边与它平行的边具有相同的权），,使原图成为欧拉图，但希望所有添加的重复边的,权的总和为最小,10,v,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,v,5,v,6,e,6,e,7,e,8,e,9,11,12,（）求出,G,1,的,最小权理想匹配,M,，得到奇次顶点的最佳配对,13,返回,14,哈 密 尔 顿 图,返回,15,推销员问题,-,定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是,推销员问题,若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题,16,定义,在加权图,G,=(,V,E,),中，,（）权最小的哈密尔顿圈称为,最佳,H,圈,（）经过每个顶点至少一次的权最小的闭通路称为,最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H,回路，长,22,最佳推销员回路，长,4,17,18,推销员问题近似算法：,二边逐次修正法,：,19,例,对以下完备图，用二边逐次修正法求较优,H,圈,20,返回,21,