歐拉圖檢視原始碼討論檢視歷史
| 歐拉圖 |
|
中文名: 歐拉圖 外文名: 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]