欧拉回路

一、欧拉回路所谓欧拉回路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设G （V ，E ）为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G 为欧拉图．在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果： 定理1 对连通图G （V ，E ），下列条件是相互等价的： （1）G 是一个欧拉图；（2）G 的每一个节点的度数都是偶数；（3）G 的边集合E 可以分解为若干个回路的并．证明 ：()()12⇒ 已知G 为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数．()()23⇒ 设G 中每一个节点的度数均为偶数．若能找到一个回路C 1使G=C 1，则结论成立．否则，令G 1=G\C 1，由C 1上每个节点的度数均为偶数，则G 1中的每个节点的度数亦均为偶数．于是在G 1必存在另一个回路C 2．令G 2=G 1\C 2，···．由于G 为有限图，上述过程经过有限步，最后必得一个回路C r 使 G r =G r-1\C r 上各节点的度数均为零，即C r =G r-1．这样就得到Ｇ的一个分解 G C C C r =⋅⋅⋅12 ．()()31⇒ 设G C C C r =⋅⋅⋅12 ，其中i C （I=1,2,…,r ）均为回路．由于G 为连通图，对任意回路i C ,必存在另一个回路j C 与之相连，即i C 与j C 存在共同的节点．现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法．二、弗罗莱算法算法步骤如下：（1）任取起始点v v R 00,;→（2）设路)},({,),,({),,({1211201rr i i r i i i v v e v v e v v e R -⋅⋅⋅=已选出，则从E\},,,{21r e e e ⋅⋅⋅中选出边1+r e ，使1+r e 与ri v 相连，除非没有其它选择，G e r r \{}+1仍应为连通的．（3）重复步骤（2），直至不能进行下去为止．定理2 连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等．三、中国邮递员问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图G （V ，E ）中，要寻找一条回路，使该回路包含G 中的每条边至少一次，且该回路的权数最小．也就是说要从包含G 的每条边的回路中找一条权数最小的回路．如果G 是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．首先注意到，若图G 有奇数度节点，则G 的奇数度节点必是偶数个．把奇数度节点分为若干对，每对节点之间在G 中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E '．令G / =G+E /，即把附加边子集E / 叠加在原图G 上形成一个多重图G /，这时G /中连接两个节点之间的边不止一条．显然G /是一个欧拉图，因而可以求出G /的欧拉回路．该欧拉回路不仅通过原图G 中每条边，同时还通过E / 中的每条边，且均仅一次．邮递员问题的难点在于当G 的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E / 的权数ω(E / )为最小？为此有下列定理．定理 3 设G （V ，E ）为一个连通的赋权图，则使附加边子集E / 的权数ω(E / )为最小的充分必要条件是G+E / 中任意边至多重复一次，且G+E / 中的任意回路中重复边的权数之和不大于该回路总权数的一半．证明： 必要性．用反证法．设存在一种奇节点集的配对，使其附加边子集E / 权数 ω(E / )为最小．若 G+E / 中有一条边重复n n ()≥2次，由于G+E /为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与 ω(E /)为最小的假设矛盾．这说明E /中的边均互不相同．其次，若G+E / 中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在E / 中删去这些重复边（注意：这些边均在E /中），而代之以该回路的其余部分的边再重复一次．经过这种替代后所得到的边子集E //仍为附加子集，且ω(E //)<ω(E /)，又产生矛盾． 充分性．设有两个附加边子集E /和E //，均使G+E /和G+E //中每条边至多重复一次，且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明ω(E /)=ω(E //)．首先注意到，由E /和E //不相同的部分组成的图（记为]\[//////）（E E EE G ）是由一个或若干个欧拉子图所组成的．这是因为E /＋E //中每个节点的度数均为偶数，而E /和E //的公共边数也是偶数，故]\[//////）（E E EE G 中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成．]\[//////）（E E EE G 的任何回路都由E /和E //中的边组成，而E /和E //在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于E /中的权数之和与属于E //中的边数之和必定相等，所以ω(E /)=ω(E //)．它就是最优附加边子集的权数，即E /和E //均为使附加边子集的权数达到最小的最优附加边子集．由定理3可得一个寻找邮递员问题最优解的方法．现举例如下：例1 已知邮递员要投递的街道如图11-20所示，试求最优邮路．解 先找出奇节点：A 1，A 2，A 3，A 4，B 1，B 2，B 3，B 4．奇节点进行配对，不妨把A 1与B 1，A 2与B 2，A 3与B 3，A 4与B 4配对，求其最短路．显然它不是最优解．下面我们根据定理3来进行调解．第一次调整：删去多于一条的重复边，即A 3与B 3，A 4与B 4中的（A 4，B 3）．调整后，实际上成为A 1与B 1，A 2与B 2，A 3与A 4，B 3与B 4的配对，它们的最短路如图11-21所示． 第二次调整：发现在回路{A 1，A 2，B 2，A 4，B 3，B 4，B 1，A 1}中重复边的权数和为11，大于该回路权数20的一半．因而调整时，把该回路的重复边删去，代之以重复其余部分，得图11-22．可以看出，实际上是调整为A 1与A 2，B 1与B 4，A 3与A 4，B 2与B 3配对．第三次调整：在图11-22中发现回路{ A 3，A 4，B 2，A 3}中重复边的权数和为7，大于该回路权数10的一半，因而删去原重复边（A 3，V 2，A 4）和（A 4，B 2），而添加（B 2，A 3），得到图11-23．进行检查发现，既没有多于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图11-23就是最优的附加边子集E /，而G+E /为欧拉图，可由弗罗莱算法找出最优邮路．在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等．上面例1题所用的求最优邮路的方法叫“奇偶点图上作业法”．因为此方法要验证每个回路，很不方便，Edmods 和Johnson 在1973年提出一种比较有效的方法，有兴趣的读者可参考有关资料．习 题 11-31．证明，若图G 为欧拉图，则G 的边数不少于节点数．2．一名邮递员的投邮区，如下图11-24所示，每条边（街道）都有邮件需投递，各边旁所注的数字为该街道的长度，试求该邮区的最短投递路径及其长度． 3．求下列图11-25（a ）(b)所示的投邮区的最佳邮路及其长度．【算法】欧拉图，欧拉回路，Eular Circuit ，随机生成欧拉图，搜索欧拉回路背景：图论起源于18世纪，1736年瑞士数学家欧拉（Eular ）发表了图论的第一篇论文“哥尼斯堡七桥问题”。

在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图(1)。

当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点。

为了解决这个问题，欧拉用ABCD四个字母代替陆地，作为4个顶点，将联结两块陆地的桥用相应的线段表示，如图(2)，于是哥尼斯堡七桥问题就变成了图(2)中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。

欧拉在论文中指出，这样的回路是不存在的。

1 定义欧拉通路(欧拉迹)——通过图中每条边一次且仅一次，并且过每一顶点的通路。

欧拉回路(欧拉闭迹)——通过图中每条边一次且仅一次，并且过每一顶点的回路。

欧拉图——存在欧拉回路的图。

2 无向图是否具有欧拉通路或回路的判定G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。

G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。

3 有向图是否具有欧拉通路或回路的判定D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。

D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。

欧拉通路、欧拉回路、欧拉图、半欧拉图的定义定义15.1通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。

具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。

从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。

在这里做个规定，即平凡图是欧拉图。

图15.1在图15.1所示各图中，e1e2e3e4e5为（1）中的欧拉回路，所以（1）图为欧拉图。

e1e2e3e4e5为（2）中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以（2）为半欧拉图。