运筹学-邮递员问题

1,中国邮递员问题,本章开始提到的邮递员问题，用图的语言来描述，就是给定一个连通图G，在每条边上有一个非负的权，要寻求一个圈，经过G的每条边至少一次，并且圈的权数最小。由于这个问题是我国菅梅谷同志于1962年首先提出来的，因此国际上长称它为中国邮递员问题。,2,一一笔画问题一笔画问题，也称为遍历问题，是很有实际意义的。设有一个连通多重图G，如果在G中存在一条链，经过G的每条边一次且仅一次，那么这条链叫做欧拉链。如在G中存在一个简单圈，经过G的每条边一次，那么这个圈叫做欧拉圈一个图如果有欧拉圈，那么这个图叫做欧拉图。很明显，一个图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链。,3,定理一个连通多重图G是欧拉图的充分必要条件是G中无奇点。证:必要性，显然。充分性，不妨设，连通多重图G至少有三点，对G的边数q用数学归纳法。因为G是连通的，并且不含奇点，故q=3。当q=3时，显然G是欧拉图。假设q=n时成立，看q=m+1的情形：由于G是无奇点的连通图，并且G的点数p=3，因此存在三个点，v,w,使得，v,w,vE。从G中去掉边，v,w,v，增加新的边，w，得到一个新的多重图G1，G1有q-1条边，且仍不含奇点，G1至多有两个分图。,4,若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有且仅有两个奇点。这个推论的证明留给读者作为习题。从这个定理的证明可以看出，识别一个连通图能否一笔画出的条件是它是否有奇点。若有奇点，就不能一笔画出。若没有奇点，就能够一笔画出，并回到原出发地。,5,比如前面提到的哥尼斯堡七桥问题，欧拉把它抽象成具有四个项点，并且都是奇点的图8.26的形状。很明显，一个漫步者无论如何也不可能重复的走完七座桥，并最终回到原出发地。图8.27。仅有两个奇点，可以一笔画出。,图8.26,B,A,D,C,图8.27,v5,v6,v4,v2,v1,v3,6,二图上作业法从一笔画问题的讨论可知，一个邮递员在他所负责投递的街道范围内，如果街道构成的图中没有奇点，那么他就可以从邮局出发，经过每条街道一次，且仅一次，并最终回到原出发地。但是，如果街道构成的图中有奇点，他就必然要在某些街道重复走几次。例如,在图8.27表示的街道图中，v1表示邮局所在地，每条街道的长度是1，邮递员可以按照以下的路线行走：,7,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上各走了两次。,8,在连通图G中，如果在边vi,vj上重复走几次，那么就在点vi,vj之间增加了几条相应的边，每条边的权和原来的权相等，并把新增加的边叫做重复边。显然，这条路线构成新图中的欧拉圈。如图8.28a,b所示。并且，邮递员的两条边走路线总路程的差等于新增加重复边总权的差。,9,v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1,图8.28,v5,v6,v4,v2,v1,v3,a,v5,v6,v4,v2,v1,v3,b,v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1,10,中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。(下略)下面我们来介绍初始邮递路线的确定，改进，以及一个邮递路线是否是最优路线的判定标准的方法-图上作业法。,11,（一）初始邮递路线的确定方法由于任何一个图中，奇点的个数为偶数，所以如果一个连通图有奇点，就可以把它们两两配成对，而每对奇点之间必有一条链（图是连通的），我们把这条链的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点，这就给出了初始投递路线。例如，在图8.29中，v1是邮局所在地，并有四个奇点v2,v4,v6,v8,将它们两两配对，比如v2和v4为一对，v6和v8为一对。,12,中国邮递员问题,v7,v6,v3,v4,v5,v8,v1,v2,图8.29,2,5,5,9,4,4,3,4,6,4,4,3,v9,13,在连接v2和v4的链中任取一条，比如链（v2,v1,v8,v7,v6,v5,v4）,在加入重复边v2,v1,v1,v8,v8,v7,v7,v6,v6,v5,v5,v4.同样，任取连接v6和v8的一条链(v8,v1,v2,v3,v4,v5,v6),在加入重复边v8,v1,v1,v2,v2,v3,v3,v4,v4,v5,v5,v6.于是，得到图8.30在连通图8.30中，没有奇点，故它是欧拉图。对于这条邮递路线，重复边的总长为:2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。,14,v7,v6,v3,v4,v5,v8,v1,v2,图8.30,2,5,5,9,4,4,3,4,6,4,4,3,v9,（v2,v1,v8,v7,v6,v5,v4）,(v8,v1,v2,v3,v4,v5,v6),15,（二）改进邮递路线，使重复边的总长不断减少。从图8.30中可以看出，在边v1,v2旁边有两条重复边，但是如果把他们都从图中去掉，所得到的连通图仍然无奇点，还是一个邮递路线，而总长度却有所减少。同理，在边v1,v8,v4,v5,v5,v6旁边的重复边也是一样的。一般地，在邮递路线上，如果在边vi,vj旁边有两条以上的重复边，从中去掉偶数条，那么可以得到一个总长度较少的邮递路线。,16,判定标准1。在最优邮递路线上，图中的每一条边至多有一条重复边。按此判定标准，将图8.30改为图8.31，这时重复边的总权减少为21。,v7,v6,v3,v4,v5,v8,v1,v2,图8-31,2,5,5,9,4,4,3,4,6,4,4,3,v9,17,不难看出，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没有奇点。因此，如果在某个圈上重复边的总权大于这个圈总权的一半，按照以上所说的作一次调整，将会得到一个总权减少的邮递路线。判定标准2。在最优邮递路线上，图中每一个圈的重复边的总权小于或者等于该圈总权的一半。,18,比如在图8.31中，圈（v2,v3,v4,v9,v2）的总权为24，但圈上重复边的总权为14，大于该圈总权的一半。因此作一次改进，在该圈上去掉重复边v2,v3,v3,v4,加上重复边v2,v9,v9,v4，如图8.32所示。这时重复边的总权减少为10。,v7,v6,v3,v4,v5,v8,v1,v2,图8.32,2,5,5,9,4,4,3,4,6,4,4,3,v9,19,20,21,从这个例子可知，一个最优邮递路线一定满足判定标准1和判定标准2。反之，不难证明，一个邮递路线如果满足判定标准1和判定标准2，那么它一定是最优邮递路线。也