欧拉图查看源代码讨论查看历史
| 欧拉图 |
|
中文名: 欧拉图 外文名: Euler Graph 发明者: 欧拉 实 质: 具有欧拉回路的图 半欧拉图: 具有欧拉通路而无欧拉回路的图 起 源: 18世纪 现代扩展: 蜘蛛图 |
欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。对欧拉图的一个现代扩展是蜘蛛图，它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区中的存在)。所以蜘蛛图允许使用欧拉图建模逻辑或的条件。[1]
起源历史
图论起源于18世纪，1736年瑞士数学家欧拉（Euler）发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题：有游人怎样不重复地走遍七桥，最后回到出发点。
为了解决这个问题，欧拉用 A,B,C,D 4个字母代替陆地，作为 4 个顶点，将联结两块陆地的桥用相应的线段表示，于是哥尼斯堡七桥问题就变成了图中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。
欧拉环游
图的环游(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
4、用 替换 F
5、end while
6、返回 W
其算法核心就是沿着一条迹往下寻找，先选择非割边，除非这个点的邻边都是割边。这样得到一条新的迹，然后再继续往下寻找，直到把所有边找完。遵循这样一个原则就可以找出图的一个欧拉环游来。
在有向图中也可以类似地定义有向环游、有向欧拉环游、有向欧拉图和有向欧拉迹的概念。
类似地，有如下定理：一个有向图是有向欧拉图当且仅当这个图中每个顶点的出度和入度相等。
相关定理
1.无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；
2.无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；
3.有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；
4.有向连通图 D 含有欧拉通路，当且仅当该图为连通图且 D 中除两个结点外，其余每个结点的入度=出度，且此两点满足 deg-(u)-deg+(v)=±1 。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）；
5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环；
6.如果图G是欧拉图且 H = G-uv，则 H 有奇数个 u,v-迹仅在最后访问 v ；同时，在这一序列的 u,v-迹中，不是路径的迹的条数是偶数。
欧拉图详解
通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。
1 定义
欧拉通路(Euler tour)——通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路 (Eulercircuit)——通过图中每条边一次且仅一次，并且过每一顶点的回路。
2 无向图是否具有欧拉通路或回路的判定
G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。
3 有向图是否具有欧拉通路或回路的判定
D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。
D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。
(注意：这里说有向图连通，说的是有向图是弱连通图。即把有向图中的边变成无向边，只要该图连通，那么原有向图即是弱连通图。实际中可用并查集判断是否弱连通)
注意下面打印节点的代码，其实打印欧拉路径的节点轨迹可以先打印每条欧拉路上的边，然后取每条边的头结点即可(最后一条边还需要取尾部结点)。
对于一般的单词首尾相连的问题，一般都是转化为有向图的欧拉通路问题(而不是无向图)，比如”给你多个单词,问你能不能将所有单词组成这样一个序列:序列的前一个单词的尾字母与后一个单词的头字母相同”，如果你把每个单词看出无向的边，那么最终求出的欧拉通路可能存在两个单词尾部和尾部相连的情况。[2]