欧拉图

数学术语

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。对欧拉图的一个现代扩展是蜘蛛图，它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区中的存在)。所以蜘蛛图允许使用欧拉图建模逻辑或的条件。

起源历史

图论起源于18世纪，1736年瑞士数学家欧拉（Euler）发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题：有游人怎样不重复地走遍七桥，最后回到出发点。

为了解决这个问题，欧拉用 A,B,C,D 4个字母代替陆地，作为 4 个顶点，将联结两块陆地的桥用相应的线段表示，于是哥尼斯堡七桥问题就变成了图中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。

欧拉环游

[Euler tour]

图的环游(tour)是指经过图的每条边至少一次的闭途位。欧拉环游是经过每条边恰好一次的环游。一个图若包含欧拉环游，则称为欧拉图(Euleriangraph)。

类似地，经过图的每条边的迹称为图的欧拉达(Enlertrail)。这些术语之所以以欧拉命名，是因为欧拉首先研究了图中欧拉迹的存在问题。1736 年欧拉解决了著名的哥尼斯堡七桥问题。把哥尼斯堡七桥问题一般化，欧拉证明了如下定理：一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数。

由此可得如下结论：一个连通图有欧拉迹当且仅当它的每个顶点的度数都是偶数，由此可得如下结论：一个连通图有欧拉迹当它至多有两个度数是奇数的顶点。

图 G 称为偶图(even graph)，如果G 中每个顶点的度数为偶数。容易发现，连通的偶图即为欧拉图。

弗勒里算法

弗勒里(B.H.Fleury) 在1883 年给出了在欧拉图中找出一个欧拉环游的多项式时间算法，称为弗勒里算法(Fleury’salgorithm)。这个算法具体表述如下：

输入：一个连通偶图 G 和 G 中任意一个指定项点 u

输出：从 u 出发的 G 的一个欧拉环游

1、令 W：=u，x：=u，F：=G

2、while

3、选一条中的边 e，其中 e 不是 F 的一条割边；如果中的边都是割边，那么任选一条边 e

4、用替换，用 y 替换 x ，用替换 F

5、end while

6、返回 W

其算法核心就是沿着一条迹往下寻找，先选择非割边，除非这个点的邻边都是割边。这样得到一条新的迹，然后再继续往下寻找，直到把所有边找完。遵循这样一个原则就可以找出图的一个欧拉环游来。

在有向图中也可以类似地定义有向环游、有向欧拉环游、有向欧拉图和有向欧拉迹的概念。

类似地，有如下定理：一个有向图是有向欧拉图当且仅当这个图中每个顶点的出度和入度相等。