Euler Circuit / Euler Path

概述

Euler Path:經過圖上所有邊剛好一次的路徑。
Euler Circuit:經過圖上所有邊剛好一次的環。
Chinese Postman Problem:經過圖上所有邊「至少一次」的環,經過的邊盡量少。

Hamilton Path:經過圖上所有點剛好一次的路徑。
Hamilton Circuit:經過圖上所有點剛好一次的環。
Travelling Salesman Problem:經過圖上所有點剛好一次的環,「邊有權重」。
Knight's Tour:移動騎士經過西洋棋盤上所有格子剛好一次的環。

Euler Circuit(Euler Tour)(Euler Cycle)
註:Euler可改為Eulerian

Euler Circuit是指一條經過圖上所有邊恰好一次的連續路線,這條路線的起點和終點要相同。也就是說,如果拿著筆沿著這條路線來描繪,可以一筆劃就畫出原圖案,還能回到當初的下筆處。

以圖論的角度來說明這件事,Euler Circuit就是涵蓋圖上所有邊(edge)恰好各一次的一個環(cycle)。也因此,在圖論領域當中,Euler Circuit也被稱作Euler Cycle。

Seven Bridges of Königsberg

http://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg

中文稱之為「七橋問題」,由著名的數學家Euler所解決。

有一說是當地居民的休閒活動就是遊覽那七座橋,大家都在嘗試找一條可以經過七座橋各一次,然後回到原處的路線。這活動蔚為風潮,許多數學家聽到這個消息後,也致力於解決這個問題,卻都無疾而終。這個問題也傳到了Euler的耳中,最後他想出了一個漂亮的證法。

另外還有一個比較長一點的童話版本:有天國王想召王宮貴族一起出去散散心,遊覽他的庭園。國王他打算從他的城堡出發,看一看他的庭園花草,以及在他庭園裡的七座橋上散散步。然後回到城堡裡去。由於天氣一定很好、陽光一定很強,屆時出發後絕不要在同一座橋上反反覆覆的走來走去,一直曬太陽,看同樣的風景,那多煩悶。

國王於是下令叫他的臣子們好好的規劃一下出遊路線,每一座橋都要參觀到,而且絕不能讓大家走同樣的橋兩次。臣子們想了很久,卻連一條路線都規劃不出來,國王只好召來聰明的數學大臣Euler來解決這個問題。Euler奉旨後,自行在家沒日沒夜的閉關了三天,終於解決了這個問題:他證明出路線不存在!

Euler當然要能向國王解釋路線為何不存在,要不然國王肯定氣得叫人把他吊起來,後果不堪設想。Euler想到,無論陸地和橋的形狀、距離、位置是如何,要找出合適的遊覽路徑,只跟橋與陸地如何連接有關係。Euler首先把庭園的地圖,簡化成我們在圖論中所看到的「圖」,點就是陸地,線(邊)就是橋。Euler發明的這張「圖」包含了充分的連接資訊,他也是第一個使用「圖」來解決問題的數學家。

接著Euler想到,如果每一座橋只能穿過一次,那麼一座橋就成了去而不回的單行道。然後,對圖上的某一個點來看,一旦從某座橋進入了一次,就要從另一座橋走出去一次,而不會一直停留在某個點上——這跟從哪裡走來、怎麼走來、哪裡出去、怎麼出去無關。所以,只要看到有個點有奇數個邊,也就是有塊陸地有奇數座橋,就表示有這塊陸地有一條橋會讓國王走得過去、卻走不出來,此時就得重複走一座橋、或不走這座橋——這就代表著國王的遊歷路線不存在。

不知道國王後來還有沒有出遊?不過Euler的這個證明過程倒是出名了。數學家們為了紀念Euler的這項貢獻,把一筆劃走完所有邊一次後恰好回到起點的路線,稱作Euler Tour,Tour即是遊覽的意思;至於Euler Circuit則是另一種較精準的用詞,Circuit即是繞一圈的意思。

偶點與奇點

偶點:連著偶數個邊的點,稱作偶點。
奇點:連著奇數個邊的點,稱作奇點。

Euler Circuit的性質:連通

一個擁有Euler Circuit的圖,則圖上所有點必定是偶點。證明就如同方才七橋問題所述。

但是,圖上所有點都是偶點,並且圖上所有點都相連通時,則此圖才擁有Euler Circuit。

Euler Circuit本身是個連通整張圖的東西,圖得連通才有可能有Euler Circuit。儘管一張圖上全是偶點,但是此圖不一定連通。

Euler Circuit的性質:拆接Euler Circuit

一個Euler Circuit在某點相交,即可在該點拆成兩個Euler Circuit:

同樣的,兩個Euler Circuit可在某點相接,合成一個Euler Circuit:

因為Euler Circuit有這種拆接性質,一個大的Euler Circuit可拆成小的,小的可接成大的——很自然的就想到Divide and Conquer。

要找出一張圖的Euler Circuit,可採用Divide and Conquer:首先想盡辦法在圖上亂繞一圈,如果這圖本身就存在Euler Circuit,則亂繞一圈後所剩的邊,一定會形成一個(或數個)Euler Circuit,而且會接在這亂繞一圈的某個(些)點上。

為何亂繞一圈是行得通的呢?在七橋問題中提到過:「然後對圖上的每一個點來看,……,這跟從哪裡走來、怎麼走來、哪裡出去、怎麼出去無關。」因此,只要確定一張圖有Euler Circuit,接著要怎麼繞都行!

亂繞一圈後,把剩下來的邊所繞出的Euler Circuit,接回一開始所亂繞的圈,就完成了此圖的Euler Circuit。

Divide:在圖上亂繞一圈,分成已繞完的邊、未繞過的邊。
Conquer:已繞完的邊看作是一張圖,是個Euler Circuit了。
         未繞過的邊看作是一張圖(或數張圖),遞迴找出那個(或那些)Euler Circuit。
Merge:把剩下來的邊繞出的那個(或那些)Euler Circuit,接回原來亂繞的那圈。

判斷無向圖是否存在Euler Circuit

判斷一張圖存不存在Euler Circuit,就等同於能不能以一筆劃畫完一張圖。這個問題在中國流傳已久,在古時候即是家家戶戶的休閒遊戲,中文稱之為「一筆劃問題」。

方法很簡單,驗證每個點都擁有偶數個邊,並且每個點都連通即可。下面是驗證每個點都擁有偶數個邊的程式碼:

至於要驗證每個點都連通,可以在實做亂繞一圈的程式時,順便來驗證一下。請繼續往下看。

從無向圖上找出一個Euler Circuit

還記得DFS可用來找出圈圈嗎?這裡採用DFS來找Euler Circuit!自己想仔細囉!

要驗證每個點都連通,則可以在找完DFS時寫段程式判斷。

時間複雜度和DFS一樣,圖所用的資料結構為adjacency matrix的話,可以以O(V^2)求出一個Euler Circuit;用adjacency list的話,可以以O(V+E)求出一個Euler Circuit。

除了DFS之外,也有其他實做方式,看倌們可自己試試。大致上就是:判斷偶點、判斷連通、亂繞一圈、連接圈圈。

從無向圖上找出全部的Euler Circuit

可以採用backtracking。無法在多項式時間內完成。

判斷有向圖是否存在Euler Circuit

每個點上出去的邊數等於進來的邊數即可。至於連通的部份,可以在找圈圈找完後再來判斷。

從有向圖上找出一個Euler Circuit

程式碼跟無向圖的差不多一樣,所以就不寫了。

從有向圖上找出所有的Euler Circuit

可以採用backtracking。無法在多項式時間內完成。

Euler Path(Euler Trail)(Euler Chain)
註:Euler可改為Eulerian

一條經過圖上所有邊(edge)的路徑(path),起點和終點不必相同、也可以相同。

Euler Circuit去掉一條邊,就形成了Euler Path。連接Euler Path的起點和終點,補上一條邊,就形成了Euler Circuit。

Euler Circuit本身也是Euler Path,是起點和終點相同的Euler Path,而且可以在任何一點當起點。

一張圖上都是偶點,並且每一點都連通時,就會有Euler Circuit。而Euler Path可由Euler Circuit刪去一條邊而得,所以只要一張圖上恰有兩個奇點、或沒有奇點,並且每一點都連通時,就會有Euler Path。是個簡單的結論。

判斷有向圖是否存在Euler Path

這張圖必須是有兩個奇點、或沒有奇點。有兩個奇點時,其中一個點會是出去的邊比進入的邊多一條,另一個點則是進入的邊比出去的邊多一條。

要驗證每個點都連通,則可以在找完DFS時寫段程式判斷。

從有向圖上找出一條Euler Path

跟找Euler Circuit一樣。還是再寫一遍好了。

找尋起點的程式碼還可以精簡成這樣:

這裡有很多奇妙的題目。

UVa 117 291 302 10054 10129 10441 10506 10596 10735

其他參考資料:http://www.mathematische-basteleien.de/house.html

Chinese Postman Problem

中國郵差問題

給定一張圖,找出一條路徑,圖上每條邊至少經過一次,且權重最小。

郵差叔叔走訪每條大街小巷,讓家家戶戶都收到信。

無向圖之演算法

http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.4.html

1. 找出圖上所有奇點,一共有偶數個。
2. 找出所有奇點點對之間的最短路徑長度。
3. 把這些奇點做最小權匹配,權重採用剛才算的最短路徑長度。
4. 把匹配邊加在原圖上,再找歐拉環,即得中國郵差路徑之權重。
5. 將匹配邊改成其代表的最短路徑,即得中國郵差路徑。

時間複雜度為五項步驟總和。各條匹配邊所代表的最短路徑,絕對不會重疊。

有向圖之演算法

1. 找出圖上所有出邊數不等於入邊數的點。
2. 於上述找到的點,找出所有點對之間的最短路徑長度。
3. 令d(x)為x點出邊數與入邊數的差值。
   把出邊數多於入邊數的點x,建立d(x)份,放在X側。
   把出邊數少於入邊數的點y,建立d(y)份,放在Y側。
   然後做最小權二分匹配,權重採用剛才算的最短路徑長度。
4. 把匹配邊加在原圖上,再找歐拉環,即得中國郵差路徑之權重。
5. 將匹配邊改成其代表的最短路徑,即得中國郵差路徑。

時間複雜度為五項步驟總和。

Hamilton Circuit / Hamilton Path

Hamilton Circuit(Hamilton Cycle)
註:Hamilton可改為Hamiltonian

Hamilton Circuit是指圖上所有點恰好都經過一次的一條連續路線,這條路線的起點和終點要相同。

以圖論的角度來看,Hamilton Circuit就是一只環。也因此,在圖論當中,Hamilton Circuit也被稱作Hamilton Cycle。

一張圖不一定只有一個Hamilton Circuit。

Hamilton Path
註:Hamilton可改為Hamiltonian

圖上所有點都恰好經過一次的一條路徑。

Hamilton Circuit去掉一條邊,就形成了Hamilton Path。連接Hamilton Path的起點和終點,補上一條邊,就形成了Hamilton Circuit。

Hamilton Circuit本身也是Hamilton Path,是起點和終點相同的Hamilton Path,而且可以在任何一點當起點。

判斷無向圖是否存在Hamilton Circuit
從無向圖上找出全部的Hamilton Circuit

判斷任意一個圖存不存在Hamilton Circuit,以及找出任意一個圖的Hamilton Circuit,這兩者都已被證明是NP-Complete問題,目前世界上尚未存在有效率的演算法可以解決這兩個問題。

暫且用backtracking試試看吧,依序列舉路徑上的各個點,時間複雜度為O(V!)。

並不是所有的圖都難以判斷出其是否存在Hamilton Circuit。有些連結性質較強的圖,容易找到Hamilton Circuit,甚至已被證明其一定含有Hamilton Circuit:http://mathworld.wolfram.com/HamiltonianCircuit.html

例如一張無向圖的所有不相鄰兩點,都滿足degree相加大於等於V,便有O(V^2)的演算法可以判斷出此圖是否含有Hamilton Circuit,並找出它。

http://www.math.fau.edu/locke/Dirac.htm
反覆進行下述操作,直到形成Hamilton Circuit為止。
如果無法操作表示此無向圖無Hamilton Circuit:

1. 若現在為路徑(p1, p2, ..., pk),
   則在路徑上找一條邊(pi, pi+1),圖上又剛好有邊(pi,pk)與邊(pi+1,p1),
   如此就去掉邊(pi, pi+1),
   形成一只環(p1, p2, ..., pi, pk, pk-1, ..., pi+1, p1)。

2. 若現在為環(p1, p2, ..., pk, p1),
   則在路徑上找一點pi,圖上又剛好有邊(pi,q)連到環外一點q,
   如此就去掉邊(pi, pi+1),
   形成一條路徑(q, pi, pi-1, ..., p2, p1, pk, pk-1, ..., pi+1)。
   或者,去掉邊(pi, pi-1),
   形成一條路徑(q, pi, pi+1, ..., pk-1, pk, p1, p2, ..., pi-1)。

Uva 775

Travelling Salesman Problem

旅行推銷員問題

一個周遊各國的商人,他想去所有不同的城市買賣東西。商人為了節省車馬費,打算從其中一個城市出發,各個地方剛好經過一次之後,回到原城市。所有城市之間都有路,請規劃出距離最短的路線,以及算出距離。這個問題其實也就是找一個權重最小的Hamilton Circuit。

最簡單的解法是使用backtracking,產生所有的地點排列方式,從中選出時間花費最短的路線。時間複雜度是O(N!),N為地點個數。

Knight's Tour

Knight's Tour

把一隻騎士放在西洋棋棋盤上,騎士能不能不重複、一筆劃地走過棋盤上六十四個方格後繞回原點:http://mathworld.wolfram.com/KnightsTour.html

此問題可看做Hamilton Circuit的特例。目前已有多項式時間演算法,給定N x M的棋盤,可以找到其中一個Knight's Tour。

Warnsdorff's Rule

每一步都走向後續路線最少的格子,但是這個方法有時會出錯。

另外可再加上:當分支數目相同時,就走向二維座標距離比較遠的格子。

【待補程式碼】

UVa 10255