歐拉迴路

如果圖G中的一個路徑包括每個邊恰好一次，則該路徑稱為歐拉路徑(Euler path)。

如果一個迴路是歐拉路徑，則稱為歐拉迴路(Euler circuit)。

具有歐拉迴路的圖稱為歐拉圖（簡稱E圖）。具有歐拉路徑但不具有歐拉迴路的圖稱為半歐拉圖。

基本介紹

• 中文名：歐拉迴路
• 外文名：Eulerian Path
• 判斷：無向圖存在歐拉迴路等
• 解法：無向圖歐拉迴路解法等
• 套用領域：信息學 圖論
• 發現者：歐拉

發現

歐拉迴路是數學家歐拉在研究著名的德國哥尼斯堡(Koenigsberg)七橋問題時發現的。如圖a所示，流經哥尼斯堡的普雷格爾河中有兩個島，兩個島與兩岸共4處陸地通過7座楊 彼此相聯。7橋問題就是如何能從任一處陸地出發，經過且經過每個橋一次後回到原出發點。

圖a

這個問題可抽象為一個如圖b所示的數學意義上的圖，其中4個結點分別表示與4塊陸土Il 對應，如結點C對應河岸C，結點A對應島A等，而結點之間的邊表示7座橋。

圖b

歐拉由此提出 了著名的歐拉定理。

1）歐拉路：通過圖中所有邊的簡單路。

2）歐拉迴路：閉合的歐拉路。

3）歐拉圖：包含歐拉迴路的圖。

判斷

以下判斷基於此圖的基圖連通。

無向圖存在歐拉迴路的充要條件

一個無向圖存在歐拉迴路，若且唯若該圖所有頂點度數都為偶數,且該圖是連通圖。

有向圖存在歐拉迴路的充要條件

一個有向圖存在歐拉迴路，所有頂點的入度等於出度且該圖是連通圖。

混合圖存在歐拉迴路條件

要判斷一個混合圖G（V,E）（既有有向邊又有無向邊）是歐拉圖，方法如下：

假設有一張圖有向圖G'，在不論方向的情況下它與G同構。並且G'包含了G的所有有向邊。那么如果存在一個圖G'使得G'存在歐拉迴路，那么G就存在歐拉迴路。

其思路就將混合圖轉換成有向圖判斷。實現的時候，我們使用網路流的模型。現任意構造一個G'。用Ii表示第i個點的入度，Oi表示第i個點的出度。如果存在一個點k，|Ok-Ik|mod 2=1，那么G不存在歐拉迴路。接下來則對於所有Ii>Oi的點從源點連到i一條容量為(Ii-Oi)/2的邊，對於所有Ii<Oi的點從i連到匯點一條容量為(Oi-Ii)/2的邊。如果對於節點U和V，無向邊（U，V）∈E，那么U和V之間互相建立容量為1的邊。如果此網路的最大流等於∑|Ii-Oi|/2，那么就存在歐拉迴路。

解法

無向圖歐拉迴路解法

求歐拉迴路的一種解法

下面是無向圖的歐拉迴路輸出代碼：注意輸出的前提是已經判斷圖確實是歐拉迴路。

C語言代碼，不全，請不要直接貼上。

int num=0;//標記輸出佇列int match[MAX];//標誌節點的度，無向圖，不區分入度和出度void solve(int x){if (match[x]==0)Record[num++]=x;else{for(int k=0;k<=500;k++){if(Array[x][k]!=0){Array[x][k]--;Array[k][x]--;match[x]--;match[k]--;solve(k);}}Record[num++]=x;}}

pascal代碼:

求無向圖的歐拉迴路（遞歸實現）

program euler;const maxn=10000;{頂點數上限}maxm=100000;{邊數上限}typetnode=^tr;tr=recordf,t:longint;{邊的起始點和終止點}al:boolean;{訪問標記}rev,next:tnode;{反向邊和鄰接表中的下一條邊}end;varn,m,bl:longint;{頂點數，邊數，基圖的極大連通子圖個數}tot:longint;g:array[1..maxn]oftnode;d:array[1..maxn]oflongint;{頂點的度}fa,rank:array[1..maxn]oflongint;{並查集中元素父結點和啟發函式值}list:array[1..maxm]oftnode;{最終找到的歐拉迴路}o:boolean;{原圖中是否存在歐拉迴路}procedurebuild(ta,tb:longint);{在鄰接表中建立邊(ta,tb)}vart1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1^.f:=ta;t1^.t:=tb;t1^.al:=false;t1^.rev:=t2;t1^.next:=g[ta];g[ta]:=t1;t2^.f:=tb;t2^.t:=ta;t2^.al:=false;t2^.rev:=t1;t2^.next:=g[tb];g[tb]:=t2;end;proceduremerge(a,b:longint);{在並查集中將a,b兩元素合併}varoa,ob:longint;beginoa:=a;whilefa[a]<>adoa:=fa[a];fa[oa]:=a;ob:=b;whilefa[b]<>bdob:=fa[b];fa[ob]:=b;ifa<>bthenbegindec(bl);{合併後，基圖的極大連通子圖個數減少1}ifrank[a]=rank[b]theninc(rank[a]);ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;end;end;procedureinit;{初始化}vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa[i]:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;proceduresearch(i:longint);{以i為出發點尋找歐拉迴路}varte:tnode;beginte:=g[i];whilete<>nildobeginifnotte^.althenbeginte^.al:=true;te^.rev^.al:=true;search(te^.t);list[tot]:=te;dec(tot);end;te:=te^.next;end;end;proceduremain;{主過程}vari:longint;begino:=false;fori:=1tondoifd[i]=0thendec(bl);{排除孤立點的影響}ifbl<>1thenexit;{原圖不連通，無解}fori:=1tondoifodd(d[i])thenexit;{存在奇點，無解}o:=true;fori:=1tondoifd[i]<>0thenbreak;tot:=m;search(i);{從一個非孤立點開始尋找歐拉迴路}end;procedureprint;{輸出結果}vari:longint;beginifnotothenwriteln('Nosolution.')elsebeginwriteln(list[1]^.f);fori:=1tomdowriteln(list[i]^.t);end;end;begininit;main;print;end.

注意record中的點的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要將record倒過來輸出。

求歐拉迴路的思路：

循環的找到出發點。從某個節點開始，然後查出一個從這個出發回到這個點的環路徑。這種方法不保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點，這條邊為起始邊，把它和當前的環銜接上。這樣直至所有的邊都被遍歷。這樣，整個圖就被連線到一起了。

具體步驟：

1。如果此時與該點無相連的點，那么就加入路徑中

2。如果該點有相連的點，那么就加入佇列之中，遍歷這些點，直到沒有相連的點。

3。處理當前的點，刪除走過的這條邊，並在其相鄰的點上進行同樣的操作，並把刪除的點加入到路徑中去。

4。這個其實是個遞歸過程。