论文--欧拉回路性质与应用探究

《论文--欧拉回路性质与应用探究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、IOI2007国家集训队论文欧拉回路性质与应用探究【摘要】　　欧拉回路，又称“一笔画”，是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识，以及求欧拉回路的算法。然后通过几个实例，介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结，指出其特点和具备的优势。【关键词】　　欧拉回路　欧拉路径【正文】一　引言欧拉回路问题是图论中最古老的问题之一。它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥（如图1）。图1市民们喜欢在这里散步，于是产生了这样一个问

2、题：是否可以找到一种方案，使得人们从自己家里出发，不重复地走遍每一座桥，然后回到家中？这个问题如果用数学语言来描述，就是在图2中找出一条回路，使得它不重复地经过每一条边。这便是著名的“哥尼斯堡七桥问题”。图2无数热衷于此的人试图解决这个问题，但均以失败告终。问题传到了欧拉（LeonhardEuler,1707-1783）那里，立即引起了这位大数学家的重视。经过悉心研究，25IOI2007国家集训队论文欧拉终于在1736年发表了论文《哥尼斯堡的七座桥》，不但成功地证明了“七桥问题”无解，而且找到了对于一般图是否存在这类回路的充要条

3、件。后人为了纪念欧拉这位伟大的数学家，便将这类回路称为欧拉回路。欧拉回路问题在信息学竞赛中有着广泛的应用，近年来在各类比赛中出现了许多与之相关的试题。本文将介绍欧拉回路的相关理论知识，并通过几道例题分析欧拉回路的实际应用。二　相关知识首先介绍相关概念和定理。设是一个图。欧拉回路　图中经过每条边一次并且仅一次的回路称作欧拉回路。欧拉路径　图中经过每条边一次并且仅一次的路径称作欧拉路径。欧拉图　存在欧拉回路的图称为欧拉图。半欧拉图　存在欧拉路径但不存在欧拉回路的图称为半欧拉图。在以下讨论中，假设图不存在孤立点度为0的顶点称为孤立点。

4、；否则，先将所有孤立点从图中删除。显然，这样做并不会影响图中欧拉回路的存在性。我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧拉路径）。对于无向图有如下结论：定理1　无向图为欧拉图，当且仅当为连通图且所有顶点的度为偶数。证明　必要性。设图的一条欧拉回路为。由于经过图的每一条边，而图没有孤立点，所以也经过图的每一个顶点，为连通图成立。而对于图的任意一个顶点，经过时都是从一条边进入，从另一条边离开，因此经过的关联边的次数为偶数。又由于不重复地经过了图的每一条边，因此的度为偶数。充分性。假设图中不存在回路，

5、而是连通图，故一定是树，那么有。由于图所有顶点的度为偶数而且不含孤立点，那么图的每一个顶点的度至少为2。由握手定理，有，与假设相矛盾。故图中一定存在回路。设图中边数最多的一条简单回路边没有重复出现的回路称为简单回路。为下面证明回路是图的欧拉回路。25IOI2007国家集训队论文假设不是欧拉回路，则中至少含有一个点，该点的度大于经过该点的关联边的次数。令，从出发有一条不属于的边。若，则顶点自身构成一个环，可以将其加入中形成一个更大的回路；否则，若，由于的度为偶数，而中经过的关联边的次数也是偶数，所以必然存在一条不属于的边。依此类推

6、，存在不属于的边。故是一条新的回路，将其加入中可以形成一个更大的回路，这与是图的最大回路的假设相矛盾。故是图的欧拉回路。由定理1可以立即得到一个用于判定半欧拉图的推论：推论1　无向图为半欧拉图，当且仅当为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。证明　必要性。设图的一条欧拉路径为　　由于经过图的每一条边，而图没有孤立点，所以也经过图的每一个顶点，为连通图成立。对于顶点，进入的次数比离开的次数少1；对于顶点，进入的次数比离开的次数多1：故和的度为奇数。而对于其它任意一个顶点，进入的次数等于离开的次数，故的度为偶数

7、。充分性。设是图中唯一的两个度为奇数的顶点。给图加上一条虚拟边得到图，则图的每一个顶点度均为偶数，故图中存在欧拉回路。从中删去得到一条从到的路径，即为图的欧拉路径。对于有向图，可以得到类似的结论：定理2　有向图为欧拉图，当且仅当的基图忽略有向图所有边的方向，得到的无向图称为该有向图的基图。连通，且所有顶点的入度等于出度。推论2　有向图为半欧拉图，当且仅当的基图连通，且存在顶点的入度比出度大1、的入度比出度小1，其它所有顶点的入度等于出度。这两个结论的证明与定理1和推论1的证明方法类似，这里不再赘述。25IOI2007国家集训队论

8、文注意到定理1的证明是构造性的，可以利用它来寻找欧拉回路。下面以无向图为例，介绍求欧拉回路的算法。首先给出以下两个性质：性质1　设是欧拉图中的一个简单回路，将中的边从图中删去得到一个新的图，则的每一个极大连通子图都有一条欧拉回路。证明　若为无向图，则图的各顶点的