资源描述：
《算法合集之《欧拉回路性质与应用探究》（终稿）.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、欧拉回路性质与应用探究湖南师大附中仇荣琦【摘要】欧拉冋路，又称笔画”，是图论中可行遍性问题的一•种。本文首先介绍了欧拉冋路的柑关理论知识，以及求欧拉冋路的算法。然后通过几个实例，介绍了与欧拉冋路和关的几类典型问题。最后对欧拉冋路的模型进行了总结，指出英特点和具备的优势。【关键词】欧拉冋路欧拉路径【正文】一引言欧拉冋路问题是图论中最古老的问题之一。它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这廉城帀，人们在两岸以及河中间的两个小岛之间建了七座桥（如图1）。从自C家里出发，不重复地走遍每就是在图2中找出J以找到一种方案，使得人们日2^市民们喜欢在这里散步
2、，于£D诃题如果用数学语言來描述,•条冋路，使得它不重复地每一-条边。这便是著名的“哥尼斯堡七桥问题”。无数热衷于此的人试图解决这Euler,1707-1783）那里,立即引起了年发表了论文《哥尼斯堡的七座桥;?。问题传到了欧拉（Leonhard】过悉心研究，欧拉终于在1736:桥问题”无解，而且找到了对于-般图是否存在这类冋路的充要条件。后人樹$纪念欧拉这位伟大的数学家，便将这类冋路称为欧拉冋路。欧拉冋路问题在信息学竞赛屮有着广泛的应用，近年來在各类比赛屮出现了许多与Z相关的试题。本文将介绍欧拉冋路的相关理论知识，并通过几道例题分析欧拉冋路的实际应用。二
3、相关知识首先介绍相关概念和定理。设G=（V,E）是一个图。欧拉回路图G中经过每条边一次并II仅一•次的冋路称作欧拉冋路。欧拉路径图G中经过每条边一次并且仅一次的路径称作欧拉路径。欧拉图存在欧拉冋路的图称为欧拉图。半欧拉图存在欧拉路径但不存在欧拉冋路的图称为半欧拉图。在以下讨论中，假设图G不存在孤立点否则，先将所有孤立点从图中删除。显然，这样做并不会影响图G中欧拉冋路的存在性。我们经曲需要判定-•个图是否为欧拉图（或半欧拉图），并且找出一•条欧拉冋路（或欧拉路径）。対于无向图有如下结论：定理1无向图G为欧拉图，当口仅当G为连通图口所有顶点的度为偶数。证明必
4、要性。设图G的一条欧拉冋路为C。山于C经过图G的每一条边，而图G没有孤立点，所以C也经过图G的每一个顶点，G为连通图成立。而对于图G的任意一个顶点「C经过u吋都是从-•条边进入，从另一条边离开，因此C经过「的关联边的次数为偶数。又山于C不重复地经过了图G的每一条边，因此v的度为偶数。充分性。假设图G中不存在冋路，HuG是连通图，故G—定是树，那么有
5、E
6、=
7、V
8、-Io山于图G所有顶点的度为偶数而且不含孤立点，那么图G的每一个顶点的度至少为2。山握手定理，有
9、E
10、=-^^（v）＞
11、V
12、,与假设相矛盾。故图G中一定存在冋路。设图G中边2veV数最多的一条简单冋
13、路2为C={ex=W（）,片）,勺=（片宀），•••，—=（%-】，％）}下面证明冋路C是图G的欧拉冋路。假设C不是欧拉冋路，则C中至少含有一个点坯，该点的度大于C经过该点的关联边的次数。令必=叫，从必出发有一•条不属于C的边£=（伽）。若片=必,则顶点必自身构成一个环，可以将其加入C中形成一•个更大的冋路；否则，若艸工必，山于艸的度为偶数，而C中经过％的关联边的次数也是偶数，所以必然存在一条不属于C的边乙=（忖）。依此类推,存在不属于C的边乙=（"；,叫=（"；十必）。故©={£；,£；,・・・,£：}是一条新的冋路，将其加入C中可以形成一•个更大的冋路
14、，这与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：故％和％的度
15、为奇数。而对于其它任意一•个顶点坯（坯工％,以工％）,P进入冬的次数等于离开坯的次数，故坯的度为偶数。充分性。设片，f是图G中唯一的两个度为奇数的顶点。给图G加上一•条虚拟边勺=（儿‘2）得到图G',则图G'的每一•个顶点度均为偶数，故图G'中存在欧拉冋路C'。从C'中删去勺得到一条从片到v2的路径P,P即为图G的欧拉路径。对于有向图，可以得到类似的结论：定理2有向图G为欧拉图，当口仅当G的基图彳连通，口所有顶点的入度等于出度。推论2有向图G为半欧拉图，当□仅当G的基图连通，口存在顶点”的入度比出度大1、卩的入度比出度小1,其它所有顶点的入度等于出度。这两
16、个结论的证明与定理1和推论I的证明方法类似，这里不再赘述。注意到定
