-
歐拉回路
鎖定
如果圖G中的一個路徑包括每個邊恰好一次，則該路徑稱為歐拉路徑(Euler path)。
具有歐拉回路的圖稱為歐拉圖（簡稱E圖）。具有歐拉路徑但不具有歐拉回路的圖稱為半歐拉圖。
- 中文名
- 歐拉回路
- 外文名
- Eulerian Path
- 判 斷
- 無向圖存在歐拉回路等
- 解 法
- 無向圖歐拉回路解法等
- 應用領域
- 信息學 圖論
- 發現者
- 歐拉
歐拉回路發現
圖1
這個問題可抽象為一個如圖2所示的數學意義上的圖，其中4個結點分別表示與4塊陸土Il 對應，如結點C對應河岸C，結點A對應島A等，而結點之間的邊表示7座橋。
圖2
1）歐拉路：通過圖中所有邊的簡單路。
2）歐拉回路：閉合的歐拉路。
歐拉回路判斷
以下判斷基於此圖的基圖連通。
無向圖存在歐拉回路的充要條件
一個無向圖存在歐拉回路，當且僅當該圖所有頂點度數都為偶數,且該圖是連通圖。
有向圖存在歐拉回路的充要條件
一個有向圖存在歐拉回路，所有頂點的入度等於出度且該圖是連通圖。
混合圖存在歐拉回路條件
要判斷一個混合圖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=record
f,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;
begin
t1:=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;
begin
oa:=a;
whilefa[a]<>adoa:=fa[a];
fa[oa]:=a;
ob:=b;
whilefa[b]<>bdob:=fa[b];
fa[ob]:=b;
ifa<>bthenbegin
dec(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;
begin
fillchar(fa,sizeof(fa),0);
fillchar(rank,sizeof(rank),0);
fillchar(d,sizeof(d),0);
readln(n,m);
fori:=1tondofa[i]:=i;
bl:=n;
fori:=1tomdobegin
readln(ta,tb);
build(ta,tb);
inc(d[tb]);
inc(d[ta]);
merge(ta,tb);
end;
end;
proceduresearch(i:longint);{以i為出發點尋找歐拉回路}
varte:tnode;
begin
te:=g[i];
whilete<>nildobegin
ifnotte^.althenbegin
te^.al:=true;
te^.rev^.al:=true;
search(te^.t);
list[tot]:=te;
dec(tot);
end;
te:=te^.next;
end;
end;
proceduremain;{主過程}
vari:longint;
begin
o:=false;
fori:=1tondo
ifd[i]=0thendec(bl);{排除孤立點的影響}
ifbl<>1thenexit;{原圖不連通，無解}
fori:=1tondo
ifodd(d[i])thenexit;{存在奇點，無解}
o:=true;
fori:=1tondo
ifd[i]<>0thenbreak;
tot:=m;
search(i);{從一個非孤立點開始尋找歐拉回路}
end;
procedureprint;{輸出結果}
vari:longint;
begin
ifnotothenwriteln('Nosolution.')elsebegin
writeln(list[1]^.f);
fori:=1tomdowriteln(list[i]^.t);
end;
end;
begin
init;
main;
print;
end.
注意record中的點的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要將record倒過來輸出。
求歐拉回路的思路：
循環的找到出發點。從某個節點開始，然後查出一個從這個出發回到這個點的環路徑。這種方法不保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點，這條邊為起始邊，把它和當前的環銜接上。這樣直至所有的邊都被遍歷。這樣，整個圖就被連接到一起了。
具體步驟：
1。如果此時與該點無相連的點，那麼就加入路徑中
2。如果該點有相連的點，那麼就加入隊列之中，遍歷這些點，直到沒有相連的點。
3。處理當前的點，刪除走過的這條邊，並在其相鄰的點上進行同樣的操作，並把刪除的點加入到路徑中去。
4。這個其實是個遞歸過程。
