中国邮递员问题算法

冯伟森Email：fws365@08十月2022离散数学计算机学院2023/2/5计算机学院2主要内容Euler图及其应用欧拉道路（回路）的定义如何判别欧拉图一个图含有欧拉道路的条件连通有向图G中含有有向欧拉道路和回路的充要条件

Fleury算法Euler图的应用(中国邮递员问题算法)

2023/2/5计算机学院3哥尼斯堡七桥问题哥尼斯堡城市有一条横贯全城的普雷格尔(Pregel)河，城的各部分用七座桥联接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题：能不能设计一次“遍游”，使得从某地动身对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地？Ab2BDCb4b1b3b5b7b62023/2/5计算机学院4Euler图定义13-1.1设G是一个无孤立结点的图，包含G的每条边的简洁道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧拉图。规定平凡图为欧拉图。明显，每个欧拉图必定是连通图。

因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。为什么？2023/2/5计算机学院5例13-1.1v5v1v2v3v4a)v5v1v2v3v4b)v4v1v2v3c)

图a是欧拉图；图b不是欧拉图，但存在欧拉道路；图c不存在欧拉道路。2023/2/5计算机学院6定理13-1.1无向连通图G＝<V，E>是欧拉图当且仅当G的全部结点的度数都为偶数。证明：“”设G是Euler图，则G必定存在一条包含全部边（也包含全部结点）的回路C，对uV，u必定在C中出现一次（可出现多次），每出现u一次，都关联着G中的两条边，而当u又重复出现时，它又关联着G中的另外的两条边，（为什么？）因而u每出现一次，都将使得结点u的度数增加2度，若u在通路中重复出现j次，则deg(u)＝2j。即u的度数必为偶数。由于在回路C中边不行能重复出现2023/2/5计算机学院7“”设连通图G的结点的度数都是偶数，则G必含有简洁回路（可对结点个数进行归纳证明）。设C是一条包含G中边最多的简洁回路：⑴若C已经包含G中全部的边，则C就是Euler回路，结论成立。⑵若C不能包含G中全部的边，则删边子图G-E（C）照旧无奇数度结点。

由于G是连通的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C′。（见示意图）Why?2023/2/5计算机学院8这样，就可以构造出一条由C和C′组成的G的回路，其包含的边数比C多，与假设冲突。因此，C必是Euler回路，结论成立。2023/2/5计算机学院9证明：“”设G具有一条Euler道路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。“”⑴若G没有奇度数结点，则结论明显成立；⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简洁道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。推论13-1.1.1非平凡连通图G＝<V，E>含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。留意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。2023/2/5计算机学院10例13-1.2由定理13-1.1及推论13-1.1.1简洁看出：是欧拉图；不是欧拉图，但存在欧拉道路；既不是欧拉图，也不存在欧拉道路。V2V1V5V3V4(a)V2V1V5V3V4(b)V1V4V2V3(c)现在，我们是不是已经解决了哥尼斯堡七桥问题？2023/2/5计算机学院11有向图的欧拉道路、欧拉图定理13-1.2ⅰ）有向连通图G含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。ⅱ）有向连通图G含有有向欧拉回路，当且仅当G中的全部结点的入度等于出度。类似于无向图的探讨，对有向图我们有以下结论：同样，有向Euler图的结点度数都为偶数；含有有向Euler道路的图仅有零个或者两个奇度数结点。2023/2/5计算机学院12例13-1.3V1V2V3V4V1V2V3V4V8V2V4V6V1V3V5V7图a)存在一条的欧拉道路：v3v1v2v3v4v1；(a)(b)(c)图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图；图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。2023/2/5计算机学院13例13-1.4解在图中，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，边数为9条。而蚂蚁甲要想走完全部的边到达c，至少要先走一条边到达b，再走一条欧拉通路，因而它至少要走10条边才能到达c，所以乙必胜。甲、乙两只蚂蚁分别位于右图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行竞赛：从它们所在的结点动身，走过图中的全部边最终到达结点c处。假如它们的速度相同，问谁先到达目的地？cb(乙)a(甲)2023/2/5计算机学院14Fleury算法（构造Euler回路）任取v0∈V，令P0＝v0；设P0＝v0e1v1e2…eivi，按下面的方法从GK=E-{e1,e2,…,ei}中选取ei+1：ei+1与vi相关联；除非无别的边可选取，否则ei+1不应当为Gk＝G-{e1,e2,…,ei}中的桥；当Gk为零图时，算法结束；否则，返回2。设G＝<V，E>是一个欧拉图即假如ei+1是割边，同时还有其它边与vi相关联，则不能选ei+12023/2/5计算机学院15例13-1.5v4v5v6e4e5e6e10e9e8e3在右图所示的欧拉图中，某人用算法求Ｇ中的欧拉回路时，走了简洁的回路：v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，无法行遍了，试分析在哪步他犯了错误？v1v3v7e1e2e7v８e1３e1２e1４e1１v2v4v5v6e4e5e6e10e9e8e3v1v3v7e1e2e7v８e1３e1２e1４e1１v2此人行遍v8时犯了能不走桥就不走桥的错误，因而未能行遍出欧拉回路。当他走到v8时，Ｇ－｛e2，e3，e14，e10，e1，e8｝,见右图，此时，e9为该图中的桥，而e7、e11均不是桥。因此，他不该走e9，而应当走e7或e11。但在行遍v3和v1时，也遇到桥，为什么没有问题呢？v9v92023/2/5计算机学院16中国邮递员问题山东师范高校，管梅谷先生1962提出并解决。（参考文献：①1962（数学通报）81.10,P32,②<电子技术应用>,81.5）一个邮递员从邮局动身，在其分管的投递区域内走遍全部的街道把邮件送到每个收件人手中，最终又回到邮局，要走怎样的线路使全程最短。这个问题用图来表示：街道为图的边，街道交叉口为图的结点，问题就是要从这样一个图中找出一条至少包含每条边一次的总长最短的回路。2023/2/5计算机学院17

对此，管梅谷曾证明，若图的边数为m，则所求回路的长度最小是m，最多不超过2m，并且每条边在其中最多出现两次。中国邮递员问题，一般为在带权连通图中找一条包括全部边的且权最小的回路。这个问题有着有效的解决方法，其中最直观的方法之一是:把图中的某些边复制成两条边，然后在所求图中找一条欧拉回路。中国邮递员问题是运筹学中一个典型的优化问题。明显，当这个图是欧拉图时，任何一条欧拉回路都符合要求；当这个图不是欧拉图时，所求回路必定要重复通过某些边。关键是：复制哪些边？2023/2/5计算机学院18算法（1）若G不含奇数度结点，则任一欧拉回路就是问题的解决。（2）若G含有2K(K>0)个奇数度结点，则先求出其中任何两点间的最短路径，然后再在这些路径之中找出K条路径P1，P2，…，PK，使得满足以下条件：①任何Pi和Pj（i≠j）没有相同的起点和终点。②在所满足①的K条最短路径的集合中，P1，P2，…PK的长度总和最短。（3）依据（2）中求出的K条最短道路P1，P2，…，PK，在原图G中复制全部出现的在这条道路上的边，设所得之图为G′。（4）构造G′的欧拉回路，即得中国邮递员问题的解。找出需复制的边连通图中，奇数度结点的个数必为偶数个。2023/2/5计算机学院19例13-1.61．因为G含有奇数度结点，所以2．G中有2K=4(K=2)个奇结点V1，V2，V3，V5。这4点间的距离

d(V1,V2)=3，d(V1,V3)=5，

d(V1,V5)=4，d(V2,V3)=2，

d(V2,V5)=3，d(V3,V5)=4各路径:V1V2(3),V3V5(4)—7V1V3(5),V2V5(3)—8V1V5(4),V2V3