资源描述：
《仇荣琦《欧拉回路性质与应用探究》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、欧拉回路性质与应用探究湖南师大附中仇荣琦【摘要】欧拉回路，乂称“一笔画”，是图论中可行遍性问题的一•种。本文首先介绍了欧拉回路的相关理论知识，以及求欧拉凹路的算法。然后通过几个实例，介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结，指出其特点和具备的优势。【关键词】欧拉凹路欧拉路径【正文】一引言欧拉凹路问题是图论中最占老的问题z_°它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛Z间建了七座桥（如图1）。市民们喜欢在这里散步，于是产生了这样一个问题：是否可以找到
2、一种方案，使得人们从自己家里出发，不重复地走遍每一廉桥，然麻回到家屮？这个问题如果用数学语言来描述,就是在图2屮找出一•条冋路，使得它不重复地经过每一•条边。这便是著名的“哥尼斯堡七桥问题”。B无数热衷于此的人试图解决这个问题，但均以失败告终。问题传到了欧拉（LeonhardEuler,1707-1783）那里，立即引起了这位大数学家的重视。经过悉心研究，欧拉终于在1736年发表了论文《哥疋斯堡的七座桥》，不但成功地证明了“七桥问题”无解，而找到了对于一般图是否存在这类回路的充要条件。麻人为了纪念欧拉这位伟人的数学家，便
3、将这类I叫路称为欧拉冋路。欧拉回路问题在信息学竞赛中有着广泛的应用，近年来在各类比赛中出现了许多与之相关的试题。本文将介绍欧拉回路的相关理论知识，并通过几道例题分析欧拉回路的实际应用。二相关知识首先介绍相关概念和定理。设G=（V,E）是一个图。欧拉回路图G中经过每条边一次并且仅一次的回路称作欧拉回路。欧拉路径图G中经过每条边一次并且仅一次的路径称作欧拉路径。欧拉图存在欧拉回路的图称为欧拉图。半欧拉图存在欧拉路径但不存在欧拉回路的图称为半欧拉图。在以下讨论小，假设图G不存在孤立点I否则，先将所有孤立点从图中删除。显然，这样
4、做并不会影响图G中欧拉回路的存在性。我们经常需要判定一个图是否为欧拉图（或半欧拉图），并找出一条欧拉回路（或欧拉路径）。对于无向图有如下结论：定理1无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。证明必要性。设图G的一条欧拉冋路为C。由于C经过图G的每一条边，而图G没冇孤立点，所以C也经过图G的每一个顶点，G为连通图成立。而对于图G的任意一•个顶点u,C经过u时都是从一条边进入，从另一条边离开，因此C经过u的关联边的次数为偶数。乂由于C不垂复地经过了图G的每一条边，因此卩的度为偶数。充分性。假设图G中不存在I叫
5、路，而G是连通图，故G—定是树，那么有
6、E
7、=
8、V
9、-1O由于图G所有顶点的度为偶数而门不含孤立点，那么图G的每一个顶点的度至少为2o由握手定理，冇困二丄工d®）n
10、v
11、,与假设相才盾。故图G中一定存在回路。设图G中边数最多的一条简单回路2为C=[e}=（v0,v,）,e2=（儿，$），•••£”=（%-」（））}1度为（）的顶点称为孤立点。2边没仃匝复出现的冋路称为简单冋路。卜•而证明回路C是图G的欧拉回路。假设C不是欧拉回路，则C中至少含有一个点*•,该点的度大于C经过该点的关联边的次数。令伕*,从必出发有一条不属于
12、C的边«=（%”）。若v；=Vq，则顶点必自身构成一个环，可以将其加入c中形成一个更大的回路；否则，若力北必，rti于K的度为偶数，而c中经过*的关联边的次数也是偶数，所以必然存在一条不属于c的边e2=（VPV2）0依此类推，存在不属于C的边&=（必，必），…,«=（%_］，%）。故C'={«，Z，是一条新的回路，将其加入C中可以形成一个更大的回路，这与C是图G的最人冋路的假设相才盾。故C是图G的欧拉冋路。由定理1町以立即得到一个用于判定半欧拉图的推论：推论1无向图G为半欧拉图，当且仅当G为连通图J1除了两个顶点的度为奇
13、数Z外,其它所有顶点的度为偶数。证明必要性。设图G的一条欧拉路径为P={©=（勺,）疋2=W*2），…，色=（%-，%）}由于P经过图G的每一条边，而图G没有孤立点，所以P也经过图G的每一个顶点,G为连通图成立。对于顶点心，P进入心的次数比离开心的次数少1；对于顶点⑰，戶进入％的次数比离开％的次数多1：故心和f的度为奇数。而对于其它任意一个顶点*（坯工弘，*工％），P进入叫的次数等于离开冬的次数，故*的度为偶数。充分性。设儿°2是图G中唯一的两个度为奇数的顶点。给图G加上一条虚拟边e（）=（v,,v2）得到图G',则图G
14、'的每一个顶点度均为偶数，故图G'中存在欧拉回路CJ从C中删去勺得到一条从v,到v2的路径P,P即为图G的欧拉路径。对于有向图，町以得到类似的结论：定理2有向图G为欧拉图，当R仅当G的基图彳连通，H.所冇顶点的入度等于出度。推论2有向图G为半欧拉图，当且仅当G的基图连通，且存在顶点比的入度比出度大1、u的入度比出度小
