对“中国邮递员问题”的数理分析

《对“中国邮递员问题”的数理分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。请为他选择一条路线，使其所行路程尽可能短。如何找到这条最短的路线，本文将逐步分析讨论这个问题。与上述问题类似的是一个哥尼斯堡七桥问题。在18世纪，东普鲁士有个城市叫哥尼斯堡，普瑞格尔河横贯其境，河中有两个美丽的小岛，全城有七座桥将河的两岸与河中两岛沟通，市民们喜欢四处散步，于是便产生这样的问题：是否可以设计一种方案，使得人们从自己家里出发，经过每座桥恰好一次，最后回到家里。热衷于这个有趣问题的人们试图解决它，但没有人能给出答案，后来数学家欧拉证明了这样的散步是不可能的。下

2、面我们把上述七桥问题转化为图论问题：一个连通图G由有限结点与连接这些结点的若干条互不相交的边组成，能否做一条连续的曲线，使得这条曲线走过所有的边恰好一次。定义经过图G的每条边恰好一次的迹称为图G的欧拉迹。图G的环游是指经过图G每条边至少一次的闭途径，欧拉环游是指经过图G每条边恰好一次的环游。一个图若包含欧拉环游，则这个图称为欧拉图。定理1一个非空连通图是欧拉图当且仅当它没有奇点。证明必要性：设图G是一个欧拉图，C是图G中一个欧拉环游，其起点(也是终点)为u。对于Av∈V(G)，v必在C上出现。因C每经过v一次，就有两条与v关联的边被使用。因为欧拉

3、环游包含图G的每条边，所以对于所有的v≠u，d(v)都是偶数。类似的，由于C开始终止于u，所以d(u)也是偶数。所以，图G没有奇点。充分性：无妨设ν(G)>1．因G连通且无奇点，故δ(G)≥2，因而必含有圈．当ν(G)=2时，设仅有的两点为u、v，则u、v间必有偶数条边，它们显然构成欧拉回路．假设ν(G)=k时，结论成立．当ν(G)=k＋1时，任取v∈V(G)．令S={v的所有关联边}．记S中的边为e1、e2、…、em，其中m=d(v)为偶数．记G'=Gv。对G'作如下操作：（1）任取ei、ej∈S，设ei=viv，ej=vjv；（2）G'：=

4、G'+vivj，S：=S{ei，ej}；（3）若S=φ，则令G'：=G'-v，停止；否则转（1）继续．这个过程最终得到的G'有k个顶点，且每个顶点在G'中的度与在G中完全一样。由归纳假设，G'中有欧拉环游，设为P。将P中上述添加边vivj都用对应的两条边ei，ej代替，显然获得G的一条欧拉环游．证毕．定理2一个连通图有欧拉迹当且仅当它最多有两个奇点。证明必要性：设连通图G有欧拉迹C，其起点和终点分别为u、v．若uv∈E(G)，则G有欧拉环游，由定理1，G无奇点．若uv∈G，则G+uv有欧拉环游，由定理1，图G+uv无奇点，故G最多只可能有两个奇

5、点．充分性：若G无奇点，则由定理1，G有欧拉环游，自然有欧拉迹．若G只有两个奇点，设其为u、v，则给G添加一条新边e=uv所得的图G+e的每个顶点都是偶点。从而G+e有欧拉环游，故G有欧拉迹．证毕．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉环游，当连通图比较复杂时就不太容易了。下面介绍一种求欧拉环游的算法．Fleury算法算法步骤如下：（1）任取起始点v0，v0→R（2）设路R={e1(v0,vi1),e2(vi1,vi2)，…，er(vir-1,vir)}已选出，则从E{e1,e2，…，er}中选出边er+1，使er+1与v

6、i相连，除非没有其它选择，Gr{er+1}仍应为连通的．（3）重复步骤（2），直至不能进行下去为止．定理3若G是欧拉图，则Fleury算法终止时得到的是G的欧拉环游．证明设G是欧拉图，Wn=v0e1v1e2…envn是Fleury算法终止时得到的迹。则显然vn在Gn=G{e1,e2，…，en}中的度数是0（因算法终止在vn，若不是0，则算法应继续）。故v0=vn（否则vn在G中是奇点，这不可能），即Wn是闭迹．若Wn不是G的欧拉环游，设S={Gn中度>0的所有顶点}。则S≠φ（因Wn不是G的欧拉环游，有边不在Wn上），且Wn上有S中的点（否则

7、Gn中Wn上的点都是Gn的孤立点，这与G是欧拉图（从而连通）矛盾），但vn∈S=V(G)S．设m是Wn上使得vm∈S而vm+1∈S的最大整数。因Wn终止于S=V(G)S，故em+1=vmvm+1是Gm中[S，S]的仅有的一条边，因而是Gm的一条割边．设e是Gm中和vm关联的另一条边（因dGn(vm)>0，这样的边e一定存在），则由算法第二步知：e必定也是Gm的一条割边（否则，按算法应选e而不选em+1），因而e是Gm[S]的割边．但由于Wn是闭迹，v0=vn∈S，且对Av∈S，dG(v)是偶数．故Gm[S]=Gn[S]中每个顶点都是偶点，由此

8、又推出Gm[S]无割边．以上两方面矛盾．证毕．下面我们把中国邮递员问题转化为图论问题：在一个连通的赋权图G（V，E）中，要寻找一条环游，