起源曆史
圖論起源于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-迹中，不是路徑的迹的條數是偶數。
