1城市道路扫雪模型.ppt

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