1城市道路扫雪模型.ppt

2/20/2017 1图论模型瑞士数学家欧拉( )在研究哥尼斯堡七桥问题的同时开创了图论研究的先河。经过两百多年的发展,尤其是在 20 世纪中叶以后,伴随着计算机科学的发展,图论也得到迅速发展和广泛应用,内容及其丰富。这里仅介绍图论中的几个最常见问题,主要目的是通过一些例子来阐述它们的应用价值。 2/20/2017 2§ 1 城镇道路扫雪模型邮递员从邮局中取出邮件,递送到不同地点,然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道,我们希望选择一条尽可能短的路线。这个问题称为中国邮递员问题,因为它是我国数学家管梅谷首先研究的。在一个网络 N=(V,E,W) 中,经过它的每条边的链称为欧拉链,经过 N中每一边至少一次的闭链称为 N的环游,经过 N中每一边恰好一次的环游称为欧拉环游。一个图能一笔画就是该图有欧拉环游。显然中国邮递员问题就是在具有非负权的网络中找出一条权最小的环游,这种环游称为最优环游。 2/20/2017 3 若N有欧拉环游,则它的每一条欧拉环游具有相同的权,它也必然是最优环游。对有欧拉环游的网络,我们可以采用弗莱里( Fleury )算法求得 N的最优环游。 弗莱里算法计算步骤如下: (1)任意选取 N的一个顶点v 0,置 Z= v 0。(2)假设链 Z=v 0e 1v 1…e iv i已选定,从 E\{ e 1 ,e 2,…,e i}中按下述方法选取 e i+1; ①e i+1和v i相关联; 2/20/2017 4 ②e i+1尽量不选 G i(是 G中去掉边 e 1,e 2,…,e i而得到的图)的割边(即去掉此边后,图 G i变为不连通),除非没有非割边可选择。 (3)设 e i+1另一关联点为v i+1。若 E\{ e 1,…,e i+1} ? , 重复步骤( 2);否则 v 1e 1v 2…e i+1v i+1即为 N的一条欧拉环游。若网络 N没有欧拉环游,此时最优环游通过的某些边将超过一次。例如图 1(a) 的图中 xuywvzwyxuwvxzyx 是最优环游,此时四条边 ux,xy,yw 和wv都被这环游通过二次。? 2/20/2017 5 1226 5122 423 423 xv w yz xv yz 12 1236 511222 (a) (b) 图1 w 2/20/2017 6 下面是一种有关引进重复边的算法。将边 e的两个端点再用一条权为 w(e )的新边连接时,称为边 e的重复边。例如把上述图(a) 中边 ux,xy,yw 和 wv 重复,得到图 1(b)。因此,中国邮递员问题可以重新叙述如下:给定一个具有非负权的网络 N, ①用添重复边的方法求得 N的一个欧拉赋权母图 N +,使得尽可能小; ②求N +的欧拉环游。??? E(N) \)N()( eeW 2/20/2017 7 解②可用弗莱里算法;解①已有好算法(爱德蒙斯 Edmonds 和约翰逊 Johnson 算法),由于这一算法比较复杂,这里就不再介绍了,有兴趣的读者可以参阅有关图论算法的书。当点数较少时,可用奇偶点图上作业法求解,为此我们不加证明介绍下述两个结论。结论 1网络 N有欧拉环游当且仅当 N中每一点的次为偶数。结论 2最优环游具有这样的性质:( 1)每条边至多重复一次;( 2)每一圈上重复边的长度不超过该圈总长的一半。当某一圈上重复边的长度超过该圈总长的一半时,将该 2/20/2017 8 圈中的所有重复边去掉,该圈中未重复的边重复,从而得奇偶点图上作业法如下: (1)若 N每一点的次均为偶数,则用弗莱里算法求得其欧拉环游,此即为 N的最优环游。(2)若不然,则用添重复边的办法得到 N的欧拉赋权母图N*。求得 N*的欧拉环游(用弗莱里算法)。(3)若某一条边在欧拉赋权母图 N*中重复多次,只要去掉该边的偶数次重复边,总可以使得该边至多重复一次,这样的图仍为欧拉赋权母图。(4)然后逐一检查 N*的每一个圈,当某一圈上重复边的长度超过该圈总长的一半时,将该圈中的所有重复边 2/20/2017 9 去掉,该圈中未重复的边重复,所得到的图也是欧拉赋权母图。例设某邮递员负责投递邮件的街道如图 2(a)所示,求出该邮递员的最短投递路线。解该网络有 8个奇点: v 2、v 4、v 5、v 7、v 8、v 9、v 11、 v 12,用添重复边的办法得图 2(b) 。按结论 2进行调整,圈v 4 v 10 v 11 v 5其总长为 12, 而重复边长为11, 此时去掉重复边 v 4 v 10、v 10 v 11、v 11 v 5 , 添加重复边v 4 v 5。同样在圈 v 2 v 3 v 9 v 7 v 6 v 2中其总长为 21,重复边长为12也超过一半。经调整后得到新的网络图 2(c)。 2/20