算法合集之《欧拉回路性质与应用探究》（终稿）.doc

欧拉回路性质与应用探究湖南师大附中 仇荣琦【摘要】欧拉冋路，又称笔画”，是图论中可行遍性问题的一•种本文首先介绍了欧拉冋路 的柑关理论知识，以及求欧拉冋路的算法然后通过几个实例，介绍了与欧拉冋路和关的几 类典型问题最后对欧拉冋路的模型进行了总结，指出英特点和具备的优势关键词】欧拉冋路欧拉路径【正文】一引言欧拉冋路问题是图论中最古老的问题之一它诞生于十八世纪的欧洲古城哥尼斯堡普 瑞格尔河流经这廉城帀，人们在两岸以及河中间的两个小岛之间建了七座桥（如图1）从自C家里出发，不重复地走遍每就是在图2中找出J以找到一种方案，使得人们日2^市民们喜欢在这里散步，于D诃题如果用数学语言來描述,•条冋路，使得它不重复地每一-条边这便是著名的“哥尼斯堡七桥问题”无数热衷于此的人试图解决这Euler, 1707-1783）那里,立即引起了年发表了论文《哥尼斯堡的七座桥;?问题传到了欧拉（Leonhard】过悉心研究，欧拉终于在1736:桥问题”无解，而且找到了对于-般图是否存在这类冋路的充要条件后人樹$纪念欧拉这位伟大的数学家，便将这类冋 路称为欧拉冋路欧拉冋路问题在信息学竞赛中有着广泛的应用，近年來在各类比赛中出现了许多与Z相 关的试题。

本文将介绍欧拉冋路的相关理论知识，并通过几道例题分析欧拉冋路的实际应用二相关知识首先介绍相关概念和定理设G = （V,E）是一个图欧拉回路 图G中经过每条边一次并II仅一•次的冋路称作欧拉冋路欧拉路径图G中经过每条边一次并且仅一次的路径称作欧拉路径欧拉图存在欧拉冋路的图称为欧拉图半欧拉图存在欧拉路径但不存在欧拉冋路的图称为半欧拉图在以下讨论中，假设图G不存在孤立点\否则，先将所有孤立点从图中删除显然， 这样做并不会影响图G中欧拉冋路的存在性我们经曲需要判定-•个图是否为欧拉图（或半欧拉图），并且找出一•条欧拉冋路（或欧 拉路径）対于无向图有如下结论：定理1无向图G为欧拉图，当口仅当G为连通图口所有顶点的度为偶数证明 必要性设图G的一条欧拉冋路为C山于C经过图G的每一条边，而图G没 有孤立点，所以C也经过图G的每一个顶点，G为连通图成立而对于图G的任意一个顶 点「C经过u吋都是从-•条边进入，从另一条边离开，因此C经过「的关联边的次数为偶 数又山于C不重复地经过了图G的每一条边，因此v的度为偶数假设图G中不存在冋路，HuG是连通图，故G—定是树，那么有|E| = |V|-Io 山于图G所有顶点的度为偶数而且不含孤立点，那么图G的每一个顶点的度至少为2。

山 握手定理，有|E| = -^^（v）＞|V|,与假设相矛盾故图G中一定存在冋路设图G中边2 veV数最多的一条简单冋路2为C = {ex =W（）,片）,勺=（片宀），•••，— =（%-】，％）}下面证明冋路C是图G的欧拉冋路假设C不是欧拉冋路，则C中至少含有一个点坯，该点的度大于C经过该点的关联边 的次数令必=叫，从必出发有一•条不属于C的边=（伽）若片=必,则顶点必自 身构成一个环，可以将其加入C中形成一•个更大的冋路；否则，若艸工必，山于艸的度为 偶数，而C中经过％的关联边的次数也是偶数，所以必然存在一条不属于C的边 乙=（忖）依此类推,存在不属于C的边乙=（"；,叫=（"；十必）故 = {；,；,・・・,：}是一条新的冋路，将其加入C中可以形成一•个更大的冋路，这与C是图 G的最大冋路的假设柑矛盾故C是图G的欧拉冋路山定理I可以立即得到一个用于判定半欧拉图的推论：推论1无向图G为半欧拉图，当口仅当G为连通图口除了两个顶点的度为奇数之外, 其它所有顶点的度为偶数证明必要性设图G的一条欧拉路径为P = { =（%,儿）疋2 =（儿宀），・・・，5 =（%」，*”）}山于P经过图G的每一条边，而图G没有孤立点，所以P也经过图G的每一个顶点，1度为o的顶点称为孤立点。

2边没旳連复出现的冋路称为简单冋路G为连通图成立对于顶点心，P进入％的次数比离开％的次数少1；对于顶点％，P进 入气”的次数比离开乙的次数多1：故％和％的度为奇数而对于其它任意一•个顶点 坯（坯工％,以工％）, P进入冬的次数等于离开坯的次数，故坯的度为偶数设片，f是图G中唯一的两个度为奇数的顶点给图G加上一•条虚拟边 勺=（儿‘2）得到图G,则图G的每一•个顶点度均为偶数，故图G中存在欧拉冋路C 从C中删去勺得到一条从片到v2的路径P , P即为图G的欧拉路径对于有向图，可以得到类似的结论：定理2有向图G为欧拉图，当口仅当G的基图彳连通，口所有顶点的入度等于出度推论2有向图G为半欧拉图，当□仅当G的基图连通，口存在顶点”的入度比出度 大1、卩的入度比出度小1,其它所有顶点的入度等于出度这两个结论的证明与定理1和推论I的证明方法类似，这里不再赘述注意到定理1的证明是构造性的，可以利用它來寻找欧拉冋路下而以尢向图为例，介 绍求欧拉冋路的算法首先给出以下两个性质：性质1设C是欧拉图G中的一个简单冋路，将C中的边从图G中删去得到一个新的 图G,则G的每一个极大连通子图都有一条欧拉冋路证明 若G为无向图，则图G的各顶点的度为偶数；若G为有向图，则图G的各顶 点的入度等于出度。

性质2设G、C?是图G的两个没有公共边，但有至少一个公共顶点的简单冋路，我 们可以将它们合并成一个新的简单冋路C o证明 只需按如图3所示的方式合并山此可以得到以下求欧J1在图G中任意找一彳2将图G中属于冋路（：3在残留图的齐极大连4将齐极大连通子图的卄刮c t倚列囹u n、j哄仅冋路图3该算法的伪代码如下：Procedure Euler-circuit （start）;Begin3忽略右向图所有边的方向，得到的无向图称为该有向图的基图For顶点start的每个邻接点v DoIf 边｛start, v)未被标记 Then Begin将边(start, v)作上标记；将边(v, sra灯)作上标记； 〃1Euler-circuit ( V);将边(start, V)加入栈S ;End;End;垠后依次取出栈S每一条边而得到图G的欧拉冋路山于该算法执行过程中每条边最多访问两次，因此该算法的时间复杂度为0(\E\) o在实际应用中，以上的实现可能导致堆栈溢出(递归的深度最多可以达到|E|层,因此 常常需要将其改造成非递归的形式完報的Pascal代码见附录1 (递归形式)和附录2 (非 递归形式)。

如果图G是有向图，我们仍然可以使用以上算法，只需将标记有〃1的行删去即可以上介绍了欧拉冋路的相关知识和算法然血实际问题中，更灵活、更具挑战性的部分 则是模型的建立下面通过剖析若干实例，探究建立欧拉冋路模型的方法，使读者対欧拉冋 路算法有更深入的认识三例题例题一单词游戏“题目描述有N个盘子，每个盘子上写着一个仅山小写字母纽成的英文单词你需要给这 些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上而咆词的末字母等于后一 个盘子上而单词的首字母请你编写一个程序，判断是否能达到这一要求如果能，请给出 一个合适的顺序数据规模I < 7V < 100000分析 通过对题目条件的一些初步分析，我们很容易得到下面的模型模型1：以N个盘子作为顶点；如果盘子A的末字母等于盘子B的首字母，那么从A向 〃连一条有向边对于样例我们可以按图4所示的方式构图这样，问题转化为在图中寻 找一条不重复地经过每个顶点的路径，即哈密尔顿路然而，求哈密尔顿路是一个十分困 难的问题，这样的模型没有给我们的解题带来任何便利因此，我们必须另辟蹊径4 题 H 來源：ACM/ICPC Central Europe Regional Contest 1999/2000,有改动malformmouse更遍历的信息——也就是 『将遍历信息表示在边上如果它的首字母为5, 勾5所示的方式构图，图 七为在图中寻找一条不重 N）时问内解决。

小结 比较以丄两个模型，模型1非常直观，模型2的建立则需要一点逆向思维：我们己经 习惯于“顶点表示元索，边表示傀］间的关系”这歹人为主的思想，HU模型2则是反英 道而行之——将元素表示在边上，血顶点则起到连获冷个元素的作用这说明，我们考虑问 题时，必须将算法进行反复地推敲、改进，其至打破旧的思维模式，大胆创新，才能找到解 决问题的最佳方法例题二仓库管理题目描述 一个公司有n家商店，每家malform啲m种商品公司有一个很大的仓库, 商品在运往商店Z前首先在这里进行整理、装箱公司将一定数量的某种商殆放到一个箱子 中，并贴上商品标签，用1〜M来标识这样，-•共有NxM个箱子，每家商丿占都将得到 标签为1〜M的箱子各一个仓库是在一个狭窄的建筑里，所以箱子只好排成一列为了 加快分发，管理员决定对箱子重新排列•个好的排列顺序应该满足以下条件：前M个箱 子具有不同的标识，以便运往1号商店；接下来M个箱子具有不同的标识，以便运往2号 商丿占……依此类推另外，初始状态时只有箱子队列的末尾才有唯一的一个空位，每一•次移 动都只能将一个箱子移动到当前的空位，并口要求所有移动结束后，空位必须冋到队尾请 你编写程序，计算重新排列所需的垠少移动次数和相应的移动方式。

数据规模1SN,M W400分析 构造二分图G ,其顶点集U = ｛卩1，卩2,…,几山｛$1，2,，其中Pi〜P”代表 〃家商丿占，代表加种商品设仓库中商店i的箱子（即从第（i-1）加+ 1个到第ix加题 H 來源：Central-European Olympiad in Informatics 2005 Day I Depot Rearrangement个箱子)中商品丿•的数最为-J，我们需要通过重新排列箱子使得所有tKj = 1 o对任意 /, j(l < i < n,l < j < m),若tj j > 1 ,那么从？•向q丿连心j 一 1条有向边，表示商店z•多了 tjj — 1个筒品八 若tjj < 1,那么从qj向□连1 条有向边，表不商丿占i少了 1 一L个商品.j O例如，样例N = 5, M =6的情况，各个箱子的排列情况如下表：413165232356214564132455123466按上述方法构造图G如下:通过分析整个重排过程中空,Pi位置；另外述可能有若干个中I笊邻两个状态Z间的若干次移动称【如此定义阶段有什么好处呢4131()523235例如，上图中冋路｛(久，么)，(么30^31；q、i和结束状态中，空位处于队尾的:置。

我们将空位处于队尾时的相芍图G中的简单回路一一对应护的操作序列为：2455123466② 24T30；41316523235；2451234656③ 319244131()523232456123465(图中蓝色格子为移动的起始位］ 血。