欧拉回路性质与应用探究.docx

欧拉回路性质与应用探究【摘要】欧拉回路，又称“一笔画”，是图论中可行遍性问题的一种本文首先介绍了欧拉回路 的相关理论知识，以及求欧拉回路的算法然后通过几个实例，介绍了与欧拉回路相关的几 类典型问题最后对欧拉回路的模型进行了总结，指出其特点和具备的优势关键词】欧拉回路 欧拉路径【正文】一引言欧拉回路问题是图论中最古老的问题之一它诞生于十八世纪的欧洲古城哥尼斯堡普 瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥(如图1)图1市民们喜欢在这里散步，于是产生了这样一个问题：是否可以找到一种方案，使得人们 从自己家里出发，不重复地走遍每一座桥，然后回到家中？这个问题如果用数学语言来描述， 就是在图2中找出一条回路，使得它不重复地经过每一条边这便是著名的“哥尼斯堡七桥 问题”图2无数热衷于此的人试图解决这个问题，但均以失败告终问题传到了欧拉(Leonhard Euler, 1707-1783)那里，立即引起了这位大数学家的重视经过悉心研究，欧拉终于在1736 年发表了论文《哥尼斯堡的七座桥》，不但成功地证明了“七桥问题”无解，而且找到了对 于一般图是否存在这类回路的充要条件后人为了纪念欧拉这位伟大的数学家，便将这类回 路称为欧拉回路。

欧拉回路问题在信息学竞赛中有着广泛的应用，近年来在各类比赛中出现了许多与之相 关的试题本文将介绍欧拉回路的相关理论知识，并通过几道例题分析欧拉回路的实际应用 二相关知识首先介绍相关概念和定理设G = (V, E)是一个图欧拉回路图G中经过每条边一次并且仅一次的回路称作欧拉回路欧拉路径图G中经过每条边一次并且仅一次的路径称作欧拉路径欧拉图存在欧拉回路的图称为欧拉图半欧拉图 存在欧拉路径但不存在欧拉回路的图称为半欧拉图在以下讨论中，假设图G不存在孤立点1；否则，先将所有孤立点从图中删除显然， 这样做并不会影响图G中欧拉回路的存在性我们经常需要判定一个图是否为欧拉图(或半欧拉图)，并且找出一条欧拉回路(或欧 拉路径)对于无向图有如下结论：定理1无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数证明 必要性设图G的一条欧拉回路为C由于C经过图G的每一条边，而图G没 有孤立点，所以C也经过图G的每一个顶点，G为连通图成立而对于图G的任意一个顶 点v，C经过v时都是从一条边进入，从另一条边离开，因^C经过v的关联边的次数为偶 数又由于C不重复地经过了图G的每一条边，因此v的度为偶数假设图G中不存在回路，而G是连通图，故G 一定是树，那么有|E = |V|-1。

由于图G所有顶点的度为偶数而且不含孤立点，那么图G的每一个顶点的度至少为2由 握手定理，有EI = 2£ d(v) > |V|，与假设相矛盾故图G中一定存在回路设图G中边 veV数最多的一条简单回路2为C = {e = (v ,v ),e = (v ,v ), ,e = (v ,v )}1 0 1 2 1 2 m m-1 0下面证明回路C是图G的欧拉回路1度为0的顶点称为孤立点2边没有重复出现的回路称为简单回路假设C不是欧拉回路，则C中至少含有一个点七，该点的度大于C经过该点的关联边 的次数令v' = v，从v'出发有一条不属于C的边e = (v', v')若v'= v'，则顶点v'自 0 k 0 10 1 10 0身构成一个环，可以将其加入C中形成一个更大的回路；否则，若v J v'，由于v'的度为 1 0 1偶数，而C中经过v'的关联边的次数也是偶数，所以必然存在一条不属于C的边 1e = (vf,v')依此类推，存在不属于c的边e = (vr,v'),...,e =(v‘，v')故2 1 2 3 2 3 k k -1 0C = {e,e'，…,e'}是一条新的回路，将其加入C中可以形成一个更大的回路，这与C是 12 k图G的最大回路的假设相矛盾。

故C是图G的欧拉回路由定理1可以立即得到一个用于判定半欧拉图的推论：推论1无向图G为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外， 其它所有顶点的度为偶数证明必要性设图G的一条欧拉路径为P = {e = (v ,v ),e = (v ,v ),...,e = (v ,v )}1 0 1 2 1 2 m m-1 m由于P经过图G的每一条边，而图G没有孤立点，所以P也经过图G的每一个顶点，G为连通图成立对于顶点v0，P进入v 0的次数比离开v 0的次数少1；对于顶点vm , P进 入vm的次数比离开v,"T次数多1：故v”pvm的度为奇数而对于其它任意一个顶点 v (v丰v , v丰v )，P进入v的次数等于离开v的次数，故v的度为偶数kk 0k m k k k充分性设v1, v2是图G中唯一的两个度为奇数的顶点给图G加上一条虚拟边 e0 = (v1,v2)得到图G，则图G的每一个顶点度均为偶数，故图G中存在欧拉回路C 从C中删去e0得到一条从v1到v2的路径P，P即为图G的欧拉路径对于有向图，可以得到类似的结论：定理2有向图G为欧拉图，当且仅当G的基图3连通，且所有顶点的入度等于出度。

推论2有向图G为半欧拉图，当且仅当G的基图连通，且存在顶点u的入度比出度 大1、v的入度比出度小1，其它所有顶点的入度等于出度这两个结论的证明与定理1和推论1的证明方法类似，这里不再赘述3忽略有向图所有边的方向，得到的无向图称为该有向图的基图注意到定理1的证明是构造性的，可以利用它来寻找欧拉回路下面以无向图为例，介 绍求欧拉回路的算法首先给出以下两个性质：性质1设C是欧拉图G中的一个简单回路，将C中的边从图G中删去得到一个新的 图G，则G的每一个极大连通子图都有一条欧拉回路证明 若G为无向图，则图G的各顶点的度为偶数；若G为有向图，则图G的各顶 点的入度等于出度性质2设C1、C2是图G的两个没有公共边，但有至少一个公共顶点的简单回路，我 们可以将它们合并成一个新的简单回路C'证明 只需按如图3所示的方式合并图3由此可以得到以下求欧拉图G的欧拉回路的算法：1在图G中任意找一个回路C；2将图G中属于回路C的边删除；3在残留图的各极大连通子图中分别寻找欧拉回路；4将各极大连通子图的欧拉回路合并到C中得到图G的欧拉回路该算法的伪代码如下：Procedure Euler-circuit (start )；BeginFor顶点start的每个邻接点v DoIf 边(start, v)未被标记 Then Begin将边(start, v)作上标记；将边(v, start)作上标记； //1Euler-circuit (v )；将边（start, v）加入栈S ；End;End;最后依次取出栈s每一条边而得到图G的欧拉回路。

由于该算法执行过程中每条边最多访问两次，因此该算法的时间复杂度为在实际应用中，以上的实现可能导致堆栈溢出（递归的深度最多可以达到|目层），因此 常常需要将其改造成非递归的形式完整的Pascal代码见附录1（递归形式）和附录2（非 递归形式）如果图G是有向图，我们仍然可以使用以上算法，只需将标记有7/1的行删去即可以上介绍了欧拉回路的相关知识和算法然而实际问题中，更灵活、更具挑战性的部分 则是模型的建立下面通过剖析若干实例，探究建立欧拉回路模型的方法，使读者对欧拉回 路算法有更深入的认识三例题例题一单词游戏4题目描述 有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词你需要给这 些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一 个盘子上面单词的首字母请你编写一个程序，判断是否能达到这一要求如果能，请给出 一个合适的顺序数据规模1 < N < 100000分析通过对题目条件的一些初步分析，我们很容易得到下面的模型模型1：以N个盘子作为顶点；如果盘子A的末字母等于盘子B的首字母，那么从A向 B连一条有向边对于样例我们可以按图4所示的方式构图这样，问题转化为在图中寻 找一条不重复地经过每一个顶点的路径，即哈密尔顿路。

然而，求哈密尔顿路是一个十分困 难的问题，这样的模型没有给我们的解题带来任何便利因此，我们必须另辟蹊径4 题目来源：ACM/ICPC Central Europe Regional Contest 1999/2000，有改动模型2：经过分析，我们发现模型1的失败之处在于，图中需要遍历的信息一也就是 每一个盘子——表示在顶点上，而顶点的遍历问题不易解决能否将遍历信息表示在边上 呢？考虑如下的构图方法：以26个字母作为顶点；对于每一个盘子，如果它的首字母为％， 末字母为2，那么从c1向c2连一条有向边对于样例我们可以按图5所示的方式构图，图 中未表示出的顶点均为孤立点，可以事先将其删去这样，问题转化为在图中寻找一条不重 复地经过每一条边的路径，即欧拉路径这个问题能够在 E\ N)时间内解决图5小结 比较以上两个模型，模型1非常直观，模型2的建立则需要一点逆向思维：我们已经 习惯于“顶点表示元素，边表示元素之间的关系”这种先入为主的思想，而模型2则是反其 道而行之——将元素表示在边上，而顶点则起到连接各个元素的作用这说明，我们考虑问 题时，必须将算法进行反复地推敲、改进，甚至打破旧的思维模式，大胆创新，才能找到解 决问题的最佳方法。

例题二仓库管理5题目描述 一个公司有N家商店，每家商店销售相同的M种商品公司有一个很大的仓库， 商品在运往商店之前首先在这里进行整理、装箱公司将一定数量的某种商品放到一个箱子 中，并贴上商品标签，用1〜M来标识这样，一共有N x M个箱子，每家商店都将得到 标签为1〜M的箱子各一个仓库是在一个狭窄的建筑里，所以箱子只好排成一列为了 加快分发，管理员决定对箱子重新排列一个好的排列顺序应该满足以下条件：前M个箱 子具有不同的标识，以便运往1号商店；接下来M个箱子具有不同的标识，以便运往2号 商店……依此类推另外，初始状态时只有箱子队列的末尾才有唯一的一个空位，每一次移 动都只能将一个箱子移动到当前的空位，并且要求所有移动结束后，空位必须回到队尾请 你编写程序，计算重新排列所需的最少移动次数和相应的移动方式数据规模1 < N, M < 400分析 构造二分图G，其顶点集V = {p , p，…，p } U {q ,q，…,q }，其中p〜p代表1 2 n 1 2 m 1 nn家商店，q1 - qm代表m种商品设仓库中商店i的箱子(即从第(i -1)m +1个到第i x m 个箱子)中商品j的数量为ttj，我们需要通过重新排列箱子使得所有t,^ = 1。

对任意i, j(1 < i < n,1 < j < m)，若t >1，那么从p向q连t -1条有向边，表示商店i多了，,j i j i, jt -1个商品j ；若t V 1，那么从q向p连1 -1条有向边，表示商店i少了 1 -1个 i, j i, j j i i, j i, j商品j例如，样例N=5， M=6的情况，各个箱子的排列情况如下表：413165232356214564132455123466按上述方法构造图G如下:5 题目来源：Central-European Olympiad in Informatics。