柯尼斯堡七橋問(wèn)題

大數(shù)學(xué)家歐拉一生中的大部分時(shí)間在俄國(guó)和普魯士度過(guò)。1735年，他提出了著名的柯尼斯堡七橋（Seven Bridges of K?nigsberg）問(wèn)題：

東普魯士柯尼斯堡（今俄羅斯加里寧格勒）的市區(qū)橫跨普雷格爾河兩岸，河中心有兩個(gè)小島，小島與河的兩岸有七座橋連接。在所有橋都只能走一遍的前提下，如何才能把這個(gè)地方所有的橋都走遍？

當(dāng)時(shí)歐拉并沒(méi)有找到這個(gè)問(wèn)題的解。第二年，他證明了不存在符合條件的走法。在論文中，歐拉將柯尼斯堡的實(shí)際情況抽象成了二維空間上點(diǎn)與線的組合，橋可以視為線（邊），橋連接的陸地視為點(diǎn)（頂點(diǎn)）——這就是數(shù)學(xué)中圖論思維的起源。

如上，柯尼斯堡七橋問(wèn)題就被推廣為“一筆畫(huà)”問(wèn)題：

對(duì)于一個(gè)給定的圖，怎樣判斷是否存在一個(gè)恰好包含了所有的邊，并且沒(méi)有重復(fù)邊的路徑？

背景鋪墊完了，下面介紹相關(guān)的概念和定理。

歐拉圖、歐拉路徑/回路

在圖論中：

• 如果在一張圖（有向圖或無(wú)向圖）上能夠不重復(fù)地遍歷完所有的邊，那么此圖就稱(chēng)為歐拉圖（Eulerian graph）。
• 能夠不重復(fù)地遍歷完所有的邊的路徑——即一筆畫(huà)的“筆畫(huà)”，稱(chēng)為歐拉路徑（Eulerian path）。
• 特別地，如果上述路徑的起點(diǎn)與終點(diǎn)相同，則稱(chēng)為歐拉回路（Eulerian circuit）。

如下gif所示的圖就是歐拉圖，存在一個(gè)歐拉路徑。

下圖是一筆畫(huà)成的“串”字，也就是說(shuō)燒烤店門(mén)口掛的這個(gè)字可以用單條LED燈帶做成。

那么柯尼斯堡七橋問(wèn)題為什么不能“一筆畫(huà)”呢？來(lái)看看歐拉提出的定理。

圖論中的歐拉定理（一筆畫(huà)定理）

歐拉同時(shí)考慮到了有向圖與無(wú)向圖的情況，因此要分別討論。

無(wú)向圖的情況

定理：

連通無(wú)向圖G有歐拉路徑的充要條件為：G中奇度頂點(diǎn)（即與其相連的邊數(shù)目為奇數(shù)的頂點(diǎn)）有0個(gè)或者2個(gè)。

證明：

• 必要性
  如果圖能夠被一筆畫(huà)成，那么對(duì)每個(gè)頂點(diǎn)，考慮路徑中“進(jìn)入”它的邊數(shù)與“離開(kāi)”它的邊數(shù)［注意前提是無(wú)向圖，所以我們不能稱(chēng)其為“入邊”和“出邊”］。很顯然這兩個(gè)值要么相同（說(shuō)明該頂點(diǎn)度數(shù)為偶），要么相差1（說(shuō)明該頂點(diǎn)度數(shù)為奇）。
  也就是說(shuō)，如果歐拉路徑不是回路，奇度頂點(diǎn)就有2個(gè)，即路徑的起點(diǎn)和終點(diǎn)；如果是歐拉回路，起點(diǎn)與終點(diǎn)重合，則不存在奇度頂點(diǎn)。必要性得證。

• 充分性

  • 如果圖中沒(méi)有奇度頂點(diǎn)，那么在G中隨機(jī)取一個(gè)頂點(diǎn)v₀出發(fā)，嘗試構(gòu)造一條回路c₀。如果c₀就是原圖，則結(jié)束；如果不是，那么由于圖是連通的，c₀和圖的剩余部分必然存在某公共頂點(diǎn)v₁，從v₁出發(fā)重復(fù)嘗試構(gòu)造回路，最終可將整張圖分割為多個(gè)回路。由于兩條相連的回路可以視為一條回路，所以該圖必存在歐拉回路。
  • 如果圖中有2個(gè)奇度頂點(diǎn)u和v，那么若是加一條邊將u和v連接起來(lái)的話，就得到一個(gè)沒(méi)有奇度頂點(diǎn)的連通圖，由上文可知該圖必存在歐拉回路，去掉這條新加的邊，就是一條以u(píng)和v為起終點(diǎn)的歐拉路徑。充分性得證。

可知，柯尼斯堡七橋問(wèn)題中的圖有4個(gè)奇度頂點(diǎn)（1個(gè)度數(shù)為5，3個(gè)度數(shù)為3），所以不存在歐拉路徑。

有向圖的情況

定理：

底圖連通的有向圖G有歐拉路徑的充要條件為：G的所有頂點(diǎn)入度和出度都相等；或者只有兩個(gè)頂點(diǎn)的入度和出度不相等，且其中一個(gè)頂點(diǎn)的出度與入度之差為1，另一個(gè)頂點(diǎn)的入度與出度之差為1。

顯然，可以通過(guò)與無(wú)向圖情況相似的思路來(lái)證明，過(guò)程略去。

歐拉定理介紹完了，那么如何找到具體的路徑呢？

尋找歐拉路徑/回路——套圈法

首先，我們當(dāng)然要判斷圖的連通性，非連通圖是不存在歐拉路徑/回路的。判斷圖的連通性可以通過(guò)傳統(tǒng)的DFS和BFS方法，也可以通過(guò)之前講過(guò)的并查集實(shí)現(xiàn)，另外還有基于傳遞閉包的Floyd-Warshall算法（沒(méi)錯(cuò)就是求最短路的那個(gè)），不再贅述。

如果圖是連通的，我們?cè)俦闅v每個(gè)頂點(diǎn)的度（有向圖就是入度和出度），根據(jù)歐拉定理即可輕松地判斷圖中是否歐拉路徑/回路。如果是歐拉路徑的話，還能順便找出路徑的起點(diǎn)和終點(diǎn)。

接下來(lái)，我們通過(guò)俗稱(chēng)“套圈法”的DFS思路來(lái)尋找歐拉路徑/回路。

參考?xì)W拉定理充分性的證明過(guò)程，歐拉圖可以分割為多個(gè)相交的回路，所以我們可以從起點(diǎn)開(kāi)始，通過(guò)DFS逐漸擴(kuò)展路徑，并標(biāo)記邊已經(jīng)被遍歷過(guò)（根據(jù)定義，已經(jīng)被標(biāo)記了的邊之后就不會(huì)再走），直到形成一個(gè)回路。然后回溯到上一個(gè)有邊沒(méi)被遍歷到的頂點(diǎn)——就是上文說(shuō)的“c₀和圖的剩余部分必然存在某公共頂點(diǎn)v₁”，以它為起點(diǎn)重復(fù)同樣的操作，直到所有回路都被找出來(lái)。在回溯階段所記錄的路徑就是所求的歐拉路徑/回路。

聽(tīng)起來(lái)似乎有些混亂，來(lái)看一道例題吧。

例題——POJ 2337 ?Catenyms?

傳送門(mén)見(jiàn)這里。

題目大意：給定N個(gè)單詞，要求把這些單詞不重復(fù)地排成一個(gè)序列，使每個(gè)單詞的首字母與前一個(gè)單詞的末尾字母相同（e.g. aloha.aloha.arachnid.dog.gopher.rat.tiger），以點(diǎn)號(hào)分隔輸出。如果存在不止一個(gè)解，輸出字典序最小的那個(gè)序列。如果沒(méi)有解，輸出三個(gè)星號(hào)。

我們可以將每個(gè)單詞的兩端視為頂點(diǎn)，單詞本身視為有向邊，就能構(gòu)造出有向圖。先判斷連通性，再判斷是否存在歐拉路徑/回路（同時(shí)找出起點(diǎn)），最后用套圈法找出具體的路徑——由于DFS回溯得到的路徑是倒序的，所以把它們放在棧中記錄比較方便。

本題需要特別注意的點(diǎn)在于輸出字典序最小的那個(gè)序列，因此先要將所有單詞按字典序排序。另外，如果存在的是歐拉回路，那么得選擇字典序最小的單詞作為起點(diǎn)。

今天時(shí)間不太夠了，AC代碼之后再補(bǔ)上，看官可參考其他大佬的代碼，或移步Discuss區(qū)。

The End

尋找歐拉路徑/回路也可以使用Fleury算法，但是它要額外檢測(cè)圖中的橋邊，相比DFS而言不太容易操作。看官可以參考圖論或離散數(shù)學(xué)教材獲取更多細(xì)節(jié)。

民那晚安。