数学建模案例分析-- 图与网络方法建模5最短投递路线的设计

《数学建模案例分析-- 图与网络方法建模5最短投递路线的设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§5最短投递路线的设计一、最优环游邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。　　在一个网络中，经过它的每条边的链称为欧拉链，经过中每一边至少一次的闭链称为的环游，经过中每一边恰好一次的环游称为欧拉环游。一个图能一笔画就是该图有欧拉环游。显然上述问题就是在具有非负权的网络中找出一条权最小的环游，这种环游称为最优环游。　　若有欧拉环游，则它的每一条欧拉环游具有相同的权，它也必然是最优环游。对有欧拉环游的网络，我们可以采用弗莱里（Fleury）算法求得

2、的最优环游。弗莱里算法　计算步骤如下：1、任意选取的一个顶点，置；2、假设链已选定，从中按下述方法选取：　（1）和相关联；　（2）尽量不选（是中去掉边而得到的图）的割边（即去掉此边后，图变为不连通），除非没有非割边可选择。3、设另一关联点为。若，重复步骤2；否则即为的一条欧拉环游。若网络没有欧拉环游，此时最优环游通过的某些边将超过一次。下面是一种有关引进重复边的算法。将边的两个端点再用一条权为的新边连接时，称为边的重复边。　　因此，问题可以重新叙述如下：给定一个具有非负权的网络，（1）用添重复边的方法求得的一个欧拉赋权母图，使得下式尽可能

3、小；（2）求的欧拉环游。　　当点数较少时，可用奇偶点图上作业法求解，为此我们不加证明介绍下述两个结论。结论1　网络有欧拉环游当且仅当中每一点的次为偶数。结论2　最优环游具有这样的性质：（1）每条边至多重复一次；（2）每一圈上重复边的长度不超过该圈总长的一半。当某一圈上重复边的长度超过该圈总长的一半时，将该圈中的所有重复边去掉，该圈中未重复的边重复，从而得奇偶点图上作业法如下：　（1）若每一点的次均为偶数，则用弗莱里算法求得其欧拉环游，此即为的最优环游。　（2）若不然，则用添重复边的办法得到的欧拉赋权母图。求得的欧拉环游（用弗莱里算法）。　

4、（3）若某一条边在欧拉赋权母图中重复多次，只要去掉该边的偶数次重复边，总可以使得该边至多重复一次，这样的图仍为欧拉赋权母图。　（4）然后逐一检查的每一个圈，当某一圈上重复边的长度超过该圈总长的一半时，将该圈中的所有重复边去掉，该圈中未重复的边重复，所得到的图也是欧拉赋权母图。二、应用举例设某邮递员负责投递邮件的街道如图1（a）所示，求出该邮递员的最短投递路线。1v2v3v5v6v8v7v9v12v13v2v5v6v8v7v9v11v12v13v2v3v5v6v8v7v9v11v13v1v4v10v1v4v10图1(a)图1(b)图1(c)

5、457444224511252v11v3v12v10v14v4该网络有8个奇点:、、、、、、、，用添重复边的办法得图1(b)。按结论2进行调整,圈其总长为12,而重复边长为11,此时去掉重复边、、,添加重复边。同样在圈中其总长为21，重复边长为12也超过一半。经调整后得到新的网络图1（c）。检查图1(c)的每一个圈,其重复边的长度均不大于该圈长的一半,因此用弗莱里算法求得图1（c）中网络的欧拉环游即为要求的最优环游。