歐拉圖

歐拉圖是指通過圖（無向圖或有向圖）中所有邊且每邊僅通過一次通路，相應的迴路稱為歐拉迴路。具有歐拉迴路的圖稱為歐拉圖（Euler Graph），具有歐拉通路而無歐拉迴路的圖稱為半歐拉圖。對歐拉圖的一個現代擴展是蜘蛛圖，它向歐拉圖增加了可以連線的存在點。這給予歐拉圖析取特徵。歐拉圖已經有了合取特徵(就是說區定義了有著與起來的那些性質的對象在區中的存在)。所以蜘蛛圖允許使用歐拉圖建模邏輯或的條件。

基本介紹

• 中文名：歐拉圖
• 外文名：Euler Graph
• 發明者：歐拉
• 實質：具有歐拉迴路的圖
• 半歐拉圖：具有歐拉通路而無歐拉迴路的圖
• 起源：18世紀
• 現代擴展：蜘蛛圖

起源歷史

圖論起源於18世紀，1736年瑞士數學家歐拉（Euler）發表了圖論的第一篇論文“哥尼斯堡七橋問題”。在當時的哥尼斯堡城有一條橫貫全市的普雷格爾河，河中的兩個島與兩岸用七座橋連結起來。當時那裡的居民熱衷於一個難題：有遊人怎樣不重複地走遍七橋，最後回到出發點。

為了解決這個問題，歐拉用 A,B,C,D 4個字母代替陸地，作為 4 個頂點，將聯結兩塊陸地的橋用相應的線段表示，於是哥尼斯堡七橋問題就變成了圖中，是否存在經過每條邊一次且僅一次，經過所有的頂點的迴路問題了。歐拉在論文中指出，這樣的迴路是不存在的。

圖1.哥尼斯堡七橋問題

歐拉環遊

[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-跡中，不是路徑的跡的條數是偶數。

圖2.