01-中国邮递员问题

中国邮递员问题厦门大学数学科学学院金贤安

引言中国邮递员问题是由山东师范大学管梅谷同志1960年首先提出的。这是数学中为数不多的几个以“中国”命名的问题或定理之一。该问题涉及著名的的哥尼斯堡(Königsberg)七桥问题。七桥问题是图论和拓扑学的起源。

引言1哥尼斯堡七桥问题2欧拉图及判定定理3Fleury算法4中国邮递员问题5奇偶点图上作业法6理论根据（选讲）哥尼斯堡七桥问题哥尼斯堡(Königsberg)今称加里宁格勒，建城于1255年，是位于波罗的海海岸的俄罗斯海港城市与加里宁格勒州的首府。加里宁格勒州位于波兰北方、立陶宛西南，原为德国东普鲁士一部分，现为俄罗斯的外飞地。图1 加里宁格勒哥尼斯堡七桥问题图2 哥尼斯堡七桥示意图有一条普雷格尔(Pregel)河流经哥尼斯堡，河上有七个桥。哥尼斯堡七桥问题一个散步者能否从某处出发走遍七个桥且每个桥只走一次，最后回到出发点？哥尼斯堡七桥问题大数学家欧拉在1736年解决了这个问题。哥尼斯堡七桥问题莱昂哈德·欧拉（LeonhardEuler，1707年4月15日－1783年9月18日）瑞士数学家和物理学家，近代数学先驱之一。欧拉是18世纪数学界最杰出的人物之一。欧拉是科学史上最多产的一位杰出的数学家，据统计他那不倦的一生，共写下了886本书籍和论文。30岁左右右眼几乎完全失明，60岁左右左眼又几乎完全失明。在1775年，他平均每周就完成一篇数学论文。1783年9月18日于俄国彼得堡去逝。欧拉Euler(1707-1783)哥尼斯堡七桥问题A将上图中A，B，C和D这四个B 区域各看成一个顶点，两区域之间有一个桥相连，就将相应的两个顶点连一条边，得到一个图。CD图3 七桥问题对应图欧拉Euler(1707-1783)欧拉图及判定定理哥尼斯堡问题即图3是否是欧拉图的问题。A给定一个连通图，我们称经过图的所有边一次且只有一次的走法为一个欧拉通路。如果进一步该走法还回到出发点，则称之为欧拉环游（回路）。具有欧拉环游的图称之为欧拉图。CBD图3 七桥问题对应图欧拉图及判定定理一笔画问题：什么样的图形可以一笔画成，笔不离纸，而且每条线都只画一次不准重复？如果一个连通图有欧拉环游，即从某个顶点出发，经过该图所有边一次，且不重复，最后回到出发点，则对中间经过的任一顶点都是一进一出，而出发点开始出去最后又进来，也是一进一出。注意有的顶点可能有若干次一进一出。不论如何，都意味着该图的每个顶点都应该是偶点（即进出总共偶数条边）。顶点可能重复经过一次 且不重复偶点一进一出欧拉图及判定定理欧拉图及判定定理定理1（判定定理）一个连通图是欧拉图当且仅当它的所有点都是偶点。思考1：如何证明充分性？对边数用归纳法。设连通图G的所有点都是偶点，则G中必定有圈C。G-E(C)的每个连通分支的每个顶点都是偶点，由归纳假设，都是欧拉图，有欧拉环游。这些欧拉环游连同C如上图所示将一起构成G的一个欧拉环游。定理1（判定定理）C1C2C3C欧拉图及判定定理Fleury算法下一步不能走⑨，为什么？①③④思考2：给定欧拉图，如何找一欧拉环游呢？⑤ ⑥② ⑦⑧输入：欧拉图GStep 1

任取G的一个顶点v0,令W0=v0。Step2设Wi=v0e1v1

…eivi已取，在E-

{e1

，

e2，

…，ei}中取ei+1使ei+1与vi关联；除非别无选择ei+1不是Gi=G-{e1

，

e2，

…，ei}的桥。设vi+1是ei+1的另一个端点。在Wi上添加ei+1和vi+1得到Wi+1。Step 3

直到Step

2不能执行时为止。输出：WmFleury算法Fleury算法思考3：如何证明Fleury算法是可行的呢？中国邮递员问题是邮递员在某一片区的信件投递路程问题。邮递员每天从邮局出发，走遍片区所有街道再返回邮局，问题是他应如何安排送信的路线可以使所走的总路程最短。中国邮递员问题以交叉路口为顶点，街道为边，街道的长度为边的权得到一赋权图，我们称之为街道图。不妨设邮局在一条街道上。若街道图是欧拉图，有欧拉环游，无需重复走街道，沿着一个欧拉环游作为投递路线即可。中国邮递员问题若街道图不是欧拉图，则有些街道需要重复走，那么中国邮递员问题就变为：重复走哪些街道，使总路程最短？中国邮递员问题用图的语言来讲，将街道图中那些边通过添加平行边使之成为欧拉图，并使得添加的平行边的总长度最短？给一个连通赋权图（权都是正的）即街道图。通过添加一些平行边，其中添加的平行边的权与原边相同，使原图变为欧拉图。求添加的平行边的总长度最短的添加方式。中国邮递员问题将使街道图成为欧拉图所添加的平行边称为一个可行方案，添加的平行边总长度最短的可行方案为最优方案。那么不难看出：(1)

在最优方案中，对街道图的任意一边，所添加的平行边的次数不会超过1。事实上，若在某可行方案中，对街道图的某边，所添加的平行边的次数大于等于2，那么在该方案中去掉该边2次，将得到一个新的更优的可行方案，矛盾。奇偶点图上作业法(2)

在最优方案中，对街道图的任意一个圈，圈上添加平行边的边的长度之和应该不超过不加平行边的边的长度之和。事实上，若在最优方案中，对街道图的某个圈，圈上添加平行边的边的长度之和大于不加平行边的边的长度之和。那么将该圈上要添加平行边的边改成不添加；不添加平行边的边改成添加，则得到一个新的更优的方案，矛盾。奇偶点图上作业法奇偶点图上作业法按下面步骤先给出一个可行方案Step

1管梅谷证明了满足上述两个条件的可行方案是最优方案并据此给出了奇偶点图上作业法。Step

1按下面步骤先给出一个可行方案找出图的所有奇点将奇点任意两两配对找出各对奇点间的一条走法将每条走法上的边都加上平行边奇偶点图上作业法判断该可行方案是否最优，即验证先给出一个可行方案Step

1Step

2奇偶点图上作业法Step

2 判断该可行方案是否最优，即验证每条边所添加的平行边的条数不超过1每个圈上添加平行边的边的总长度不超过不加平行边的边的总长度奇偶点图上作业法Step

1Step

2Step

3不是最优方案最优方案奇偶点图上作业法Step

3 按下面的方法调整方案得到一个更优的可行方案若一条边添加的平行边数大于等于2，则去掉偶数条使其至多只有一条平行边若有一圈平行边的总长度超过非平行边的总长度，则将该圈上平行边改为非平行边，非平行边改为平行边奇偶点图上作业法Step

1Step

2Step

3不是最优方案最优方案新的可行方案奇偶点图上作业法图上作业法主要困难在于要检验街道图的所有圈是否满足条件(2)，而当街道图比较复杂时，圈的数目会很大。74122243例：2 353step

1step

3奇偶点图上作业法step

21973年Edmonds和Johnson给出了中国邮递员问题的一个更好的解决方法。奇偶点图上作业法理论依据（选讲）引理1：欧拉图的边集是一些边不交的圈的边的并。思考：如何证明？设G是欧拉图，取它的一个欧拉环游，从一个顶点出发沿欧拉环游前进，第一次遇到顶点重复时，形成一个圈，去掉该圈上的边，继续前行，再次遇到顶点重复时，形成另一个圈，该圈与前面的圈边不交，去掉该圈上的边，继续前行，以此类推可证。定理2：若两个可行方案a,b（都是街道图的边子集）都满足上述两个条件，则这两个方案的边的总长度相同。理论依据（选讲）由于满足条件(1)，a和b都是街道图的边集的子集，不会是多重的。设原街道图为G，则G+a和G+b都是欧拉图。设c是a和b的公共边，即c=a∩b。令G'=G[a+b-c]，则在G'的任意一个圈上，由条件(2)，a中边的总长度等于b中边的总长度（为什么？）。另一方面，G'的每个顶点都是偶点，因此G'是由一些边不交的圈构成的（引理1）。这就得到a-c和b-c的边的总长度相同，因此两个可行方案的边的总长度相同。理论依据（选讲）推论:

满足上述两个条件的可行方案是最优方案。证明:设a是任意一个满足上述两条件的一个可行方案，b是最优方案。由b是最优方案可得b也满足上述两条件。由定理2，a和b这两个方案的边的总长度相同因此