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

《对_中国邮递员问题_的数理分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、科技经济市场技术平台对“中国邮递员问题”的数理分析金毅(苏州工业职业技术学院，江苏苏州215104)摘要：如果一个非空连通图G是一个欧拉图，则很容易由Fleury算法求出一个欧拉环游，但是若图G不是欧拉图，即存在奇点，则中国邮递员问题的解决要困难得多。本文的主要目标是给出在有奇点的连通图中寻找最小权数的环游的方法．关键词：奇点；环游；欧拉环游一位邮递员从邮局出发投递邮件，经过他所管辖的每条街证明必要性：设连通图G有欧拉迹C，其起点和终点分别道至少一次，然后回到邮局。请为他选择一条路线，使其所行路为u、v．程尽可能短。如何找到这条最短的路线，本文将逐步分析讨论这若

2、uv∈E(G)，则G有欧拉环游，由定理1，G无奇点．个问题。若uv∈G，则G+uv有欧拉环游，由定理1，图G+uv无奇点，与上述问题类似的是一个哥尼斯堡七桥问题。在18世纪，故G最多只可能有两个奇点．东普鲁士有个城市叫哥尼斯堡，普瑞格尔河横贯其境，河中有两充分性：若G无奇点，则由定理1，G有欧拉环游，自然有欧个美丽的小岛，全城有七座桥将河的两岸与河中两岛沟通，市民拉迹．们喜欢四处散步，于是便产生这样的问题：是否可以设计一种方若G只有两个奇点，设其为u、v，则给G添加一条新边案，使得人们从自己家里出发，经过每座桥恰好一次，最后回到e=uv所得的图G+e的每个顶点都

3、是偶点。从而G+e有欧拉环家里。热衷于这个有趣问题的人们试图解决它，但没有人能给出游，故G有欧拉迹．证毕．答案，后来数学家欧拉证明了这样的散步是不可能的。利用定理1去判断一个连通图是否为欧拉图比较容易，但下面我们把上述七桥问题转化为图论问题：一个连通图G要找出欧拉环游，当连通图比较复杂时就不太容易了。下面介绍由有限个结点与连接这些结点的若干条互不相交的边组成，能一种求欧拉环游的算法．否做一条连续的曲线，使得这条曲线走过所有的边恰好一次。Fleury算法定义经过图G的每条边恰好一次的迹称为图G的欧拉算法步骤如下：迹。图G的环游是指经过图G每条边至少一次的闭途径，欧

4、拉（1）任取起始点v0，v0→R环游是指经过图G每条边恰好一次的环游。一个图若包含欧拉（2）设路R={e1(v0,vi1),e2(vi1,vi2)，…，er(vir-1,vir)}已选出，则从E环游，则这个图称为欧拉图。定理1一个非空连通图是欧拉图当且仅当它没有奇点。{e1,e2，…，er}中选出边er+1，使er+1与vi相连，除非没有其它选证明必要性：设图G是一个欧拉图，C是图G中一个欧拉择，Gr{er+1}仍应为连通的．环游，其起点(也是终点)为u。对于Av∈V(G)，v必在C上出现。（3）重复步骤（2），直至不能进行下去为止．因C每经过v一次，就有两

5、条与v关联的边被使用。因为欧拉环定理3若G是欧拉图，则Fleury算法终止时得到的是G游包含图G的每条边，所以对于所有的v≠u，d(v)都是偶数。类的欧拉环游．似的，由于C开始终止于u，所以d(u)也是偶数。所以，图G没有证明设G是欧拉图，Wn=v0e1v1e2…envn是Fleury算法终奇点。充分性：无妨设ν(G)>1．因G连通且无奇点，故δ(G)≥2，止时得到的迹。则显然vn在Gn=G{e1,e2，…，en}中的度数是0因而必含有圈．（因算法终止在vn，若不是0，则算法应继续）。故v0=v（否则nvn当ν(G)=2时，设仅有的两点为u、v，则u、v间必有

6、偶数条在G中是奇点，这不可能），即Wn是闭迹．边，它们显然构成欧拉回路．若Wn不是G的欧拉环游，设S={Gn中度>0的所有顶点}。假设ν(G)=k时，结论成立．当ν(G)=k＋1时，任取v∈V(G)．令S={v的所有关联边}．则S≠φ（因Wn不是G的欧拉环游，有边不在Wn上），且Wn上记S中的边为e1、e2、…、em，有S中的点（否则Gn中Wn上的点都是Gn的孤立点，这与G是其中m=d(v)为偶数．记G'=Gv。对G'作如下操作：欧拉图（从而连通）矛盾），但vn∈S=V(G)S．设m是Wn上使得（1）任取ei、ej∈S，设ei=viv，ej=vjv；vm∈S

7、而vm+1∈S的最大整数。因Wn终止于S=V(G)S，故（2）G'：=G'+vivj，S：=S{ei，ej}；em+1=vmvm+1是Gm中[S，S]的仅有的一条边，因而是Gm的一条割（3）若S=φ，则令G'：=G'-v，停止；否则转（1）继续．边．这个过程最终得到的G'有k个顶点，且每个顶点在G'中设e是Gm中和vm关联的另一条边（因dGn(vm)>0，这样的度与在G中完全一样。由归纳假设，G'中有欧拉环游，设为P。的边e一定存在），则由算法第二步知：e必定也是Gm的一条割将P中上述添加边vivj都用对应的两条边ei，ej代替，显然获得边（否则，按算法应选

8、e而不选em+1），因而