运筹学邮递员问题.ppt

中国邮递员问题 本章开始提到的邮递员问题，用图的语言来描述，就是给定一个连通图G，在每条边上有一个非负的权，要寻求一个圈，经过G的每条边至少一次，并且圈的权数最小。由于这个问题是我国菅梅谷同志于1962年首先提出来的，因此国际上长称它为中国邮递员问题。 一．一笔画问题 一笔画问题，也称为遍历问题，是很有实际意义的。 设有一个连通多重图G，如果在G中存在一条链，经过G的每条边一次且仅一次，那么这条链叫做欧拉链。如在G中存在一个简单圈，经过G的每条边一次，那么这个圈叫做欧拉圈一个图如果有欧拉圈，那么这个图叫做欧拉图。很明显，一个图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链。 定理 一个连通多重图G是欧拉图的充分必要条件是G中无奇点。 证:必要性，显然。 充分性，不妨设，连通多重图G至少有三点，对G的边数q用数学归纳法。因为G是连通的，并且不含奇点，故q=3。 当q=3时，显然G是欧拉图。假设q=n时成立，看q=m+1的情形：由于G是无奇点的连通图，并且G的点数p=3，因此存在三个点μ，v,w,使得[μ，v],[w,v]∈E。从G中去掉边[μ，v],[w,v]，增加新的边[μ，w]，得到一个新的多重图G1，G1有q-1条边，且仍不含奇点，G1至多有两个分图。 若G1是连通的，则由归纳假设，G1有欧拉圈C1。把C1中的边[w,μ]换成[μ,v],[w,v]，即是G中的欧拉圈。若G1有两个分图G1’，G1’’，令v在G1’中。由归纳假设，G1’，G1’’分别有欧拉圈C1’，C1’’，把C1”中的边[μ,w]换成[μ,v],C1’及[v,w]即是G中的欧拉圈。 推论 一个多重连通图G有欧拉链的充分必要条件是G有且仅有两个奇点。 这个推论的证明留给读者作为习题。 从这个定理的证明可以看出，识别一个连通图能否一笔画出的条件是它是否有奇点。若有奇点，就不能一笔画出。若没有奇点，就能够一笔画出，并回到原出发地。  比如前面提到的哥尼斯堡七桥问题，欧拉把它抽象成具有四个项点，并且都是奇点的图8.26的形状。很明显，一个漫步者无论如何也不可能重复的走完七座桥，并最终回到原出发地。图8.27。仅有两个奇点，可以一笔画出。  二．图上作业法 从一笔画问题的讨论可知，一个邮递员在他所负责投递的街道范围内，如果街道构成的图中没有奇点，那么他就可以从邮局出发，经过每条街道一次，且仅一次，并最终回到原出发地。但是，如果街道构成的图中有奇点，他就必然要在某些街道重复走几次。 例如,在图8.27表示的街道图中，v1表示邮局所在地，每条街道的长度是1，邮递员可以按照以下的路线行走：  v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1, 总长是12。 也可以按照另一条路线走： v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1, 总长是11。 按照第1条路线走，在边[v2,v4],[v4,v6],[v6,v5]上各走3两次，按照第2条路线走，在边[v3,v2],[v3,v5]上各走了两次。 在连通图G中，如果在边[vi,vj]上重复走几次，那么就在点vi,vj之间增加了几条相应的边，每条边的权和原来的权相等，并把新增加的边叫做重复边。显然，这条路线构成新图中的欧拉圈。如图8.28a, b所示。并且，邮递员的两条边走路线总路程的差等于新增加重复边总权的差。 v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1 中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。 我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。 (下略) 下面我们来介绍初始邮递路线的确定，改进，以及一个邮递路线是否是最优路线的判定标准的方法-----图上作业法。  （一）初始邮递路线的确定方法 由于任何一个图中，奇点的个数为偶数，所以如果一个连通图有奇点，就可以把它们两两配成对，而每对奇点之间必有一条链（图是连通的），我们把这条链的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点，这就给出了初始投递路线。 例如，在图8.29中，v1是邮局所在地，并有四个奇点v2,v4,v6,v8,将它们两两配对，比如v2和v4为一对，v6和v8为一对。 中国邮递员问题 在连接v2和v4的链中任取一条，比如链（v2,v1,v8,v7,v6,v5,v4）,在加