起源历史
图论起源于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.
其算法核心就是沿着一条迹往下寻找，先选择非割边，除非这个点的邻边都是割边。这样得到一条新的迹，然后再继续往下寻找，直到把所有边找完。遵循这样一个原则就可以找出图的一个欧拉环游来。
在有向图中也可以类似地定义有向环游、有向欧拉环游、有向欧拉图和有向欧拉迹的概念。
类似地，有如下定理：一个有向图是有向欧拉图当且仅当这个图中每个顶点的出度和入度相等。
相关定理
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-迹中，不是路径的迹的条数是偶数。
