柯尼斯堡七橋問題

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

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

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

如上窃肠，柯尼斯堡七橋問題就被推廣為“一筆畫”問題：

對于一個給定的圖，怎樣判斷是否存在一個恰好包含了所有的邊刷允，并且沒有重復(fù)邊的路徑冤留？

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

歐拉圖纤怒、歐拉路徑/回路

在圖論中：

• 如果在一張圖（有向圖或無向圖）上能夠不重復(fù)地遍歷完所有的邊，那么此圖就稱為歐拉圖（Eulerian graph）天通。
• 能夠不重復(fù)地遍歷完所有的邊的路徑——即一筆畫的“筆畫”泊窘，稱為歐拉路徑（Eulerian path）。
• 特別地，如果上述路徑的起點與終點相同烘豹，則稱為歐拉回路（Eulerian circuit）瓜贾。

如下gif所示的圖就是歐拉圖，存在一個歐拉路徑携悯。

下圖是一筆畫成的“串”字祭芦，也就是說燒烤店門口掛的這個字可以用單條LED燈帶做成。

那么柯尼斯堡七橋問題為什么不能“一筆畫”呢憔鬼？來看看歐拉提出的定理龟劲。

圖論中的歐拉定理（一筆畫定理）

歐拉同時考慮到了有向圖與無向圖的情況，因此要分別討論逊彭。

無向圖的情況

定理：

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

證明：

• 必要性
  如果圖能夠被一筆畫成，那么對每個頂點侮叮，考慮路徑中“進(jìn)入”它的邊數(shù)與“離開”它的邊數(shù)［注意前提是無向圖，所以我們不能稱其為“入邊”和“出邊”］悼瘾。很顯然這兩個值要么相同（說明該頂點度數(shù)為偶）囊榜，要么相差1（說明該頂點度數(shù)為奇）。
  也就是說亥宿，如果歐拉路徑不是回路卸勺，奇度頂點就有2個，即路徑的起點和終點烫扼；如果是歐拉回路曙求，起點與終點重合，則不存在奇度頂點映企。必要性得證悟狱。

• 充分性

  • 如果圖中沒有奇度頂點，那么在G中隨機(jī)取一個頂點v₀出發(fā)堰氓，嘗試構(gòu)造一條回路c₀挤渐。如果c₀就是原圖，則結(jié)束双絮；如果不是浴麻，那么由于圖是連通的，c₀和圖的剩余部分必然存在某公共頂點v₁囤攀，從v₁出發(fā)重復(fù)嘗試構(gòu)造回路软免，最終可將整張圖分割為多個回路。由于兩條相連的回路可以視為一條回路焚挠，所以該圖必存在歐拉回路膏萧。
  • 如果圖中有2個奇度頂點u和v，那么若是加一條邊將u和v連接起來的話，就得到一個沒有奇度頂點的連通圖向抢，由上文可知該圖必存在歐拉回路认境，去掉這條新加的邊，就是一條以u和v為起終點的歐拉路徑挟鸠。充分性得證叉信。

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

有向圖的情況

定理：

底圖連通的有向圖G有歐拉路徑的充要條件為：G的所有頂點入度和出度都相等覆享；或者只有兩個頂點的入度和出度不相等佳遂，且其中一個頂點的出度與入度之差為1，另一個頂點的入度與出度之差為1撒顿。

顯然丑罪，可以通過與無向圖情況相似的思路來證明，過程略去凤壁。

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

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

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

如果圖是連通的迹卢，我們再遍歷每個頂點的度（有向圖就是入度和出度），根據(jù)歐拉定理即可輕松地判斷圖中是否歐拉路徑/回路绞绒。如果是歐拉路徑的話婶希，還能順便找出路徑的起點和終點。

接下來蓬衡，我們通過俗稱“套圈法”的DFS思路來尋找歐拉路徑/回路喻杈。

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

聽起來似乎有些混亂攒钳，來看一道例題吧帮孔。

例題——POJ 2337 ?Catenyms?

傳送門見這里。

題目大意：給定N個單詞不撑，要求把這些單詞不重復(fù)地排成一個序列文兢，使每個單詞的首字母與前一個單詞的末尾字母相同（e.g. aloha.aloha.arachnid.dog.gopher.rat.tiger），以點號分隔輸出焕檬。如果存在不止一個解姆坚，輸出字典序最小的那個序列。如果沒有解实愚，輸出三個星號兼呵。

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

本題需要特別注意的點在于輸出字典序最小的那個序列乎赴，因此先要將所有單詞按字典序排序。另外潮尝，如果存在的是歐拉回路榕吼，那么得選擇字典序最小的單詞作為起點。

今天時間不太夠了勉失，AC代碼之后再補上，看官可參考其他大佬的代碼顽素，或移步Discuss區(qū)徒蟆。

The End

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

民那晚安。