图和网络第二讲

第二讲 欧拉图和哈米尔顿图及匹配问题

§1-2-4 欧拉图及其应用

欧拉在1763年解决著名的Konigsberg七桥难题中，建立了欧拉图类存在性的完整理论。图论的研究方法也随之进入了数学的广大领域。

Konigsberg是18世纪时东普鲁士的一个城市，Pregel河流经该市，并把该市陆地分成了4个部分：两岸及两个河心岛。陆地间共有七座桥相通，如图1-2-4.1（a）所示。长期以来人们一直在议论一个话题：能否从任何一块陆地出发，通过每座桥一次且仅一次，最后又返回出发点？尽管人们做了许多试验，但没有一人成功。欧拉把这个实际问题转化为图1-2-4.1(b)所示的一个图论问题，他用结点A，B，C，D分别表示对应的陆地，用边来表示连接陆地的桥。这样，七桥问题等价于在图1-2-4.1(b)中找寻一条包括每条边一次的回路，或者说，从图中任一点出发，一笔把图画出来（每边只能经过一次）。欧拉证明，七桥问题具有否定的答案，从而解决了这一难题。下面介绍解决这一问题的基本思想。

A A B C B C

D

(a)

D 图1-2-4.1

(b)

定义 1-2-4.1 设G是一个无向图，包含G每条边的简单道路称为欧拉道路；包含G每条边的简单回路称为欧拉回路；具有欧拉回路的图称为欧拉图。

显然，每个欧拉图必然是连通图。

定理 1-2-4.1 连通图G是欧拉图当且仅当G不含奇数度结点。

证明： 设G是欧拉图，则必然存在一条包含每条边的回路C，当沿着回路C朝一个方向前进时，必定沿一条边进入某结点后再沿另一条边由这个结点出去，即每个结点都和偶数条边关联，因此G的结点都是偶数度结点。

反过来，设连通图G的结点都是偶数度结点，则G含有回路。设C是一条

C

1

C/

图1-2-4.2

包含G中最多边的回路。若C包含了G的全部边，则G是欧拉图的结论成立。如果C不能包含G的全部边，则删边子图G-E（C）仍无奇数度结点。由于G是连通的的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C?（如图1-2-4.2所示）。这样，就可以由C和C?构造出G的一条包含边数C多的回路，与C的最大性假设矛盾。因此，G中包含边数最多的回路必是欧拉回路，即是说，不含奇数度结点的连通图是欧拉图。

推论 1-2-4.1.1 非平凡连通图G含有欧拉道路当且仅当G最多有两个奇数度结点。

证明： 设连通图G含有一条欧拉道路L，则在L中除起点与终点外，其余每个结点都与偶数条边相关联，因此，G中最多有两个奇数度的结点。

反过来，若G没有奇数度结点，显然有一条欧拉道路；若G有两个奇数度结点u和v，则G+uv是欧拉图，从而存在欧拉回路C。从C中去掉边vu，则得到一条简单道路L，其起点是u，终点是v，并且包含了G的全部边，即L是G的一条欧拉道路。

由定理4-2-4.1 及其推论知道，因为图1-2-4.1(b)中没有偶数度结点，不存在欧拉回路，甚至也不存在欧拉道路，所以Koningsberg七桥问题有否定的结论。

无向图的欧拉道路问题及其有关结果很容易推广到有向图中去，这时，我们考虑的是有向欧拉道路和有向欧拉回路。

定理 1-2-4.2 连通有向图G含有有向欧拉回路当且仅当G中每个结点的入度等于出度 ，连通有向图G含有有向欧拉道路当且仅当除两个结点外，其余每个结点的入度等于其出度，而这两个结点中一个结点的入度比其出度多1，另一结点的入度比其出度少1。

这个定理的证明与定理4-2-4.1及其推论的证明类似。显然，一条有向欧拉回路进入任何一个结点的次数和离开这个结点的次数应该一样，因此有向欧拉图的顶点度数也是偶数。同样，含有向欧拉道路的图最多有两个奇数度结点。

对于一个已知的欧拉图G=（V，E），可以按下述方式构成一条欧拉回路。设置两个变量s和e，分别表示当前位于的结点和要经历的边。

由欧拉图G=（V，E）构造欧拉回路算法：

1．从G中任选一点v0和与v0关联的边e0，置s?v0,e?e0

2．记录s和e，并在G中标记e。设与e关联的另一结点为u0，置s?u0。

2

3．设从G中删去已标记过的全部k条边后得到的子图为Gk，则 3.1 当Gk为零图时，算法结束。

3.2 若在Gk中与s关联的边都不是割边，则任选其中一边e?，置e?e?，转2。

3.3 若在Gk中与s关联的边有割边e?且s是Gk中的一度点，则令e?e?，转2；否则在Gk中任选一条与s关联的非割边e//，令e?e??，转2。

这种构造欧拉回路的方法对于有向欧拉图和无向欧拉图同样适用，下面将用例子说明。欧拉图的一个应用例子就是所谓模数转换问题。

e0=0000 000 e1=0001 001 e8=1000 e9=1001 100 e2=0010 a b

c d

e3=0011 e5=0101 101 010 e4=0100 e10=1010 e13=1101 110 e12=1100 e11=1011 011 e6=0110 e7=0111 111 e14=1110 e15=1111 图1-2-4.3

图1-2-4.4

例 设一个旋转鼓的表面分成了16个扇形段（图1-2-4.3），每个扇段用导体材料或者绝缘材料构成，分别表示0和1两种状态。现在要用四位的二进制数abcd给出a对应段的位置，要怎样安排或设置0和1两种状态的扇段，才能使16个扇段的位置号码各不相同？也就是说，如何把16个0或1排成一个循环，使得按同一方向由4个依次相连的0或1能够组成0000~1111中的每一个二进码？

3

这个问题可以这样来考虑：如图1-2-4.4，用8个结点分别表示000~111的八个二进码，若结点u的二进码为a1a2a3，结点v的二进码为a2a3a4，则（u，v）是有向图的一条边，这条边对应于四位的二进码a1a2a3a4。通过这种办法可以构造出一个有8个结点16条边的有向图，这16条边分别对应于0000~1111的16个二进码，且边（u,v）的二进码的后三位与边（v,w）的二进码的前三位相同。因此，上述找由16个0或1组成的循环，正好对应于在图1-2-4.4中找一条有向欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。

现在按前面找欧拉回路的算法列表如下：

顺序 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 当前所在结点s 000 000 001 010 101 011 110 100 001 011 111 111 110 101 010 100 当前标记边e e0 e1 e2 e5 e11 e6 e12 e9 e3 e7 e15 e14 e13 e10 e4 e8 由图中得到一条欧拉回路C，其边序列为 e0,e1,e2,e5,e11,e6,e12,e9,e3,e7,e15,e14, e13,e10,e4,e8，由此得到对应的16个0或1的排列方式0000101100111101。

另一个与欧拉图有密切关系的应用问题是由管梅谷先生1962年提出的所谓“中国邮递员问题”。考虑的是一个邮递员从邮局出发，在其分管的投递区域内走遍所有的街道把邮件送到每个收件人手中，最后又回到邮局，要走怎样的路线使全程最短？这个问题可以用图来表示：以街道为图的边，以街道交叉口为图的

4

结点，问题就是要从这样一个图中找出一条至少包含每个边一次的总长最短的闭道路。显然当这个图是欧拉图时，任何一条欧拉回路都符合要求；但是，当这个图不是欧拉时，所求闭道路必然要重复通过某些边。对此，管梅谷曾证明若图的边数为m，则所求闭道路的长度最少是m，最多不超过2m，并且每条边在其中最多出现两次。中国邮递员问题还可以进一步推广到带权的连通图上，即在带权图中找一个包括全部边且权最小的闭道路。

一般意义下的中国邮递员问题是运筹学中一个典型的优化问题，这个问题有着有效的解决办法，其中最直观的方法之一是把图中的某些边复制成两条边，然后在所得图中找一个欧拉回路，这个回路即是原来问题的解。下面仅对无向介绍算法的基本思想：

求解无向图的中国邮递员问题算法。

（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中复制所有出现在这k条道路上的边，设所得之图为G?。

（4）构造G?的欧拉回路，即得到中国邮递员问题的解。 例 图1-2-4.5中G含有4个奇数度结点；

d(v1)?3,d(v2)?5,d(v3)?3,d(v5)?5。求得距离

从d(v1,v2)?3,d(v1,v3)?5,d(v1,v5)?4,d(v2,v3)?2,d(v2,v5)?3,d(v3,v5)?4。中选出两条长度总和最小的道路p1?v1v7v5和p2?v2v3，构造图G?，则中国邮递员问题的一个解便是回路C?v1v7v3v2v4v5v6v2v7v5v3v2v1v7v5v1。

求中国邮递员问题的算法中，包含了两个基本的优化算法：求任意两点的距离及求最佳匹配，它们都有对应的有效算法。

5

本文来源：https://www.bwwdw.com/article/oyb2.html