配送路線可能需要經過每條街道,但容許重複經過路口。這是關於邊的問題,不同於尋找經過每個頂點的哈密頓(Hamilton)圈。這裏討論有限簡單無向圖。
定義 2.1.1
(跡與歐拉迴路)
跡是不重複邊的遊走;歐拉(Euler)迴路是恰好經過每條邊一次的閉跡。
對沒有邊而至少有一個頂點的圖,約定長度為零的遊走是迴路;排除空頂點集。
定理/命題
定理 2.1.2
(歐拉迴路的偶度判據)
至少有一條邊的有限圖存在歐拉迴路,當且僅當所有正度頂點屬於同一連通分支,且每個頂點的度數都是偶數。孤立頂點不影響路線。
證明
(配對進入邊與離開邊)
迴路連接所有邊的端點。每次經過頂點都使用一條進入邊和一條不同的離開邊;起點的最後進入邊與最初離開邊配對。因此每個頂點的關聯邊被分成若干對,度數為偶數。
證明
(閉合並拼接未用邊的跡)
從正度頂點出發,沿未使用的邊前進,直到無邊可用。此跡必定回到起點:在其他頂點,已用的關聯邊由此前訪問的一對對邊及最後一條進入邊組成;偶數度保證還存在未用的離開邊。若所有邊已用完則結束。否則,由正度頂點連通,可找到當前閉跡上的頂點與未用邊相接:從閉跡沿路徑走向某條未用邊,取路徑上的第一條未用邊。刪去閉跡的邊後,每個頂點減少的度數都是偶數,故剩餘圖仍為偶數度。從該頂點沿未用邊走出另一個閉跡,拼入原跡。每次拼接至少用掉一條新邊,邊數有限,最終覆蓋全部邊。
常見錯誤
(只需正度頂點之間連通)
要求整個圖連通過強:三角形加一個孤立頂點仍有經過全部邊的迴路。反之,兩個不相交三角形的度數全為偶數,卻沒有一條跡能覆蓋兩個分支。兩個條件各有作用。
例題詳解
例題 2.1.3
(共享一個頂點的兩個三角形)
兩個三角形 和 只共享頂點 。各點度數依次為 ,歐拉迴路為 。容許重複頂點 ,沒有邊重複;它不是哈密頓圈,因為閉合前 出現兩次。
練習
快速檢查
(連通圖能否恰有一個奇數度頂點?)
解答 · 答案
不能。每條邊有兩個端點,所以度數之和為 。一個整數和為偶數,當且僅當奇數項的數目為偶數。
快速檢查
(證明:恰有兩個奇數度頂點 的連通圖有一條從 到 、恰好經過每條邊一次的跡。)
解答 · 答案
添加新頂點 及邊 。擴充圖所有頂點均為偶數度,正度頂點連通,故有歐拉迴路。把迴路旋轉成從 開始,再刪去首尾兩條邊,即 的僅有兩條關聯邊,剩餘跡恰好經過每條原邊一次,端點為 ;必要時反向。使用新頂點無須假設 原本不是邊。
開跡與奇數度條件
定理 2.1.4
(開放跡的兩奇度頂點判據)
迴路定理也給出開放歐拉跡的完整判別法。設圖至少有一條邊,所有正度頂點在同一分支。存在恰好經過每條邊一次且兩個端點不同的跡,當且僅當恰有兩個奇數度頂點;這兩個頂點就是跡的端點。
證明
(兩端未配對的邊)
必要性來自配對:在每次內部訪問時,把進入邊與離開邊配對。起點有一條未配對的離開邊,終點有一條未配對的進入邊,其餘邊均配對,所以恰有這兩個奇數度頂點。跡在結束前重複經過端點也不影響論證,因為中間的訪問仍貢獻成對的邊。充分性已在關於兩個奇點之間歐拉跡的練習中用添加輔助頂點並刪去其兩條關聯邊證明。使用新頂點可以避免在原本已有 時加入重邊。
沒有奇數度頂點時,從正度頂點出發並覆蓋每條邊的跡必須回到起點。有四個奇數度頂點的圖不可能由一條跡覆蓋全部邊,但可能由多條跡共同覆蓋。正度頂點之間的連通性也不能省略:兩條互不相連的邊有四個奇數度頂點,兩個互不相連的三角形沒有奇數度頂點,兩者都沒有覆蓋全部邊的一條跡。
例題 2.1.5
(懸掛邊產生兩個奇數度頂點)
在共享 的兩個三角形 上添加懸掛邊 。 的度數變為 5 和 1,其餘頂點的度數仍為 2。一條開放歐拉跡是 。它以兩個奇數度頂點為端點。不能從 開始走完全部邊,因為端點必須是 。
由證明得到算法
拼接閉跡證明了存在性,但若每次都在整條路線中重新尋找插入位置,就可能浪費許多時間。堆疊(stack)記錄尚未處理完的頂點出現位置,隱式完成插入:先處理完一段沿未用邊走出的路線,再返回較早的位置。同一頂點的不同次出現是不同的堆疊項目。
先假設圖至少有一條邊,所有正度頂點在同一分支,且每個頂點的度數均為偶數。選正度頂點 為起點。給 條邊各分配一個不同的編號;在邊的兩個端點的鄰接表中,都記錄另一端及同一個邊編號。每條邊只有一個布林(Boolean)標記 used[e],兩個端點共用它,而不是分別標記。每個頂點各有一個鄰接表游標,初始指向第一項。
堆疊操作的精確定義
堆疊初始只有 ,輸出列表 初始為空。只要堆疊非空,就令 為頂部頂點,執行以下操作。
- 將 的游標向前移動,略過邊已標記為使用的項目。
- 若仍有項目 ,將游標移過該項,把 標記為已用,並將 的一次新出現壓入堆疊。
- 否則彈出頂部這一次出現的 ,把 加到 的末尾。
堆疊清空時,把 反轉,得到路線。每個壓入的項目還可以記錄進入它所用的邊編號;彈出時依次記錄這些編號,略去最初項目的空編號,再把邊編號列表反轉,就得到相應的邊順序。
以後再次訪問同一頂點時,不得把游標重設。彈出也不會把任何邊改回未用。堆疊遵循後進先出:彈出後,算法回到此前的位置,該位置的頂點可能已經出現過多次。
定理 2.1.6
(堆疊算法返回歐拉迴路)
在上述連通性和偶數度假設下,反轉後的輸出是從 出發的閉跡,恰好使用全部 條邊各一次,共有 次頂點出現。
為甚麼彈出的順序能夠拼成路線
證明
(每個階段都回到起點)
把連續的壓入操作分成若干階段:一個階段從目前頂部出發,在下一次彈出之前結束。最初,未用邊構成的圖處處為偶數度。若階段從 出發,卻在 處無法繼續,則本階段用掉的邊在 處貢獻奇數度;階段開始前那裏為偶數度,因此還應剩下一條未用邊,矛盾。於是每個非空階段都回到其起點;沒有壓入的階段則直接留在原處。刪去閉跡的邊會使各點度數減少偶數,所以一個完整階段結束後,未用邊圖又處處為偶數度。這個歸納只討論完整階段;單次壓入過程中,剩餘度數未必是偶數。
因此,第一個彈出的頂點是 。再考慮以後任意一次彈出。上一個頂點位置 被彈出後,若堆疊未空,它此前的項目 成為頂部。進入這一次 的堆疊邊連接 。在下一次彈出前插入的壓入階段從 出發並回到 ,所以下一個彈出的頂點就是 。因此, 中相鄰兩項總是相鄰頂點,連接它們的邊正是較早彈出項目的進入邊。每個新項目有一條不同的進入邊,而且每個項目只彈出一次。故 以及它的反轉都恰好使用每條已選擇的邊一次。最初的底部項目沒有進入邊,且最後才彈出,所以 的最後一項也是 ;反轉後的路線從 出發並回到 。
還須證明沒有漏選邊。每個到達過的頂點最終都會在沒有未用關聯邊時彈出。假如正度分支中仍有一條未用邊,取從 到它某個端點的路徑。若路徑上的邊全已選擇,該端點已經到達;否則,路徑上第一條未選邊的前一個端點已經到達。兩種情況都與已到達頂點的關聯邊已用盡矛盾。故起始項目之後共壓入 次,合計彈出 次。
證明透視
彈出規定插入次序,並非再次走過邊
彈出不表示實際沿已用邊倒著走一遍,而是記錄各個頂點位置的完成順序。在 處探索的閉合繞行,會在輸出反轉後插入這一次 的位置。邊標記保證不重複用邊;剩餘圖的奇偶性保證反向彈出列表能夠接起來。這是證明中兩個不同的環節。
例題 2.1.7
(追蹤共享頂點的兩個三角形)
邊為 ,從 出發,先選擇第一個三角形的邊。堆疊先變為 。最後的 沒有未用邊,於是彈出,得到 ,堆疊為 。此時 仍有未用邊,沿 壓入,得到 。頂部 的邊已用盡,彈出它。繼續彈出後得到
反轉後為 ,正是在 中插入 得到的迴路。暫時的輸出 並不表示全部邊已覆蓋;較早的一次 仍在堆疊上等待處理。
執行時間與開放跡
在鄰接表模型下,總共有 個項目。每個游標只向前移動,所以累計越過至多 項,其中包括已從另一端選擇的邊。每條邊引起一次壓入,每個堆疊項目引起一次彈出和追加。反轉需要 次操作。統計度數及預先搜尋正度頂點的連通性都只需 時間。因此,若頂點和邊的編號支援常數時間存取,整個過程的時間和空間均為 。這裏 包括孤立頂點。若改用鄰接矩陣,並讓每個頂點的游標在其對應行中只向前移動,則至多檢查 個單元,得到 的實現。若每次訪問頂點都從頭掃描整行,開銷可能更大;表示方式和游標規則都不能忽略。
對於奇數度端點為 的開放跡,使用前面已證明的輔助構造:添加新頂點 和邊 ,從 執行迴路算法,再刪去首尾兩條邊。由於 度數為二,它在此迴路中只會出現在開始和結束處。剩餘部分是以 為端點、只用原圖邊的跡;若方向不合要求,再反轉。只增加一個頂點和兩條邊,不改變線性時間界。對有頂點但無邊的圖,單獨返回該頂點即可。
練習:檢查實現是否正確
快速檢查
(圖是兩個互不相連的三角形,程式從其中一個三角形出發。返回序列確實是一條閉跡,為甚麼仍不能接受為整個圖的歐拉迴路?)
解答 · 答案
六條邊中只有三條被選擇,頂點出現次數為四,而不是七。另一個分支不可到達。證書必須覆蓋給定圖的整個邊集,而不只是給出一條閉跡。預先檢查正度頂點連通性就會拒絕這個輸入。
快速檢查
(省略奇偶檢查,對中心為 、葉子為 的三邊星圖,從 出發。先選 ,再選 ,彈出 後再選 。反轉輸出會發生甚麼?)
解答 · 答案
彈出列表為 ,反轉後為 。雖然三條邊都已標記,列表也恰有 次頂點出現,但 不是邊。四個奇數度頂點不符合任何一種歐拉判別法。因此,僅檢查邊數和邊標記,不能證明返回的頂點序列正確;還須核對相鄰端點及所聲稱的邊編號。定理中的奇偶假設才是壓入階段能夠閉合的保證。
歐拉性質不等於哈密頓性質
概念視角組合
邊與頂點回答不同的問題
歐拉迴路恰好使用每條邊一次;哈密頓圈在返回起點前恰好訪問每個頂點一次。兩者不同。上面共享一個頂點的兩個三角形是歐拉圖,卻沒有哈密頓圈:刪去共享頂點後圖不連通,而從哈密頓圈刪去任意一個頂點後,剩下的邊是一條經過其餘所有頂點的路徑。因此含哈密頓圈的圖刪去任一頂點後仍連通。這是必要條件,一般不是充分條件。
反過來,四頂點完全圖有哈密頓圈 ,但每個頂點度數為 3,故沒有歐拉迴路。它有六條邊,所寫的哈密頓圈只使用四條。經過每個頂點的閉遊走也不自動是哈密頓圈,因為它可能重複頂點。
快速檢查
(正方形 加對角線 。求開放歐拉跡所有可能端點,並給出一條跡。)
解答 · 答案
各點度數依次為 ,所以唯一可能的端點是 。一條跡為 ,四條正方形邊和對角線各用一次。
快速檢查
(圖由一個三角形和一個獨立的孤立頂點組成。它有歐拉迴路嗎?有經過全部四個頂點的哈密頓圈嗎?)
解答 · 答案
三角形本身就是歐拉迴路,因為孤立頂點沒有需要覆蓋的邊。不存在經過全部四個頂點的哈密頓圈:孤立頂點沒有可供進入或離開的邊。這一比較使用了孤立頂點不妨礙歐拉迴路的約定。
常見錯誤
常見錯誤
(第一條閉跡未必完整)
在所有度數為偶數的假設下,沿未用邊前進直到無法繼續會得到閉跡,但第一條閉跡不一定包含全部邊。在共享頂點的兩個三角形中, 已經閉合,且 沒有未用關聯邊,另一個三角形卻尚未使用。此時停止會得到不完整答案;在 處拼接是把局部閉跡與剩餘邊連接起來的關鍵步驟。
這也說明連通性在論證中有兩個作用。它是單條路線到達所有邊端點的必要條件;在構造證明中,它還保證當前跡上有可連接未用邊的位置。取跡上頂點 ,從它沿路徑走向一條未用邊的端點。若路徑的邊均已用過,其終點已在跡上,且連接未用邊。否則,路徑上第一條未用邊的前一個端點在跡上,因為此前的路徑邊均已用過。因此總能找到拼接點。
快速檢查
(某圖有一個度為 5 的頂點,其他頂點度數都是偶數。這可能嗎?)
解答 · 答案
不可能。度數之和將是奇數,與 矛盾;無論圖是否連通都成立。這並不意味著只要奇數度頂點數為偶數就存在歐拉跡:四個奇數度頂點已排除單條歐拉跡。
快速檢查
(對共享頂點的兩個三角形,直接驗證 是歐拉迴路。)
解答 · 答案
相鄰頂點形成的邊依次是 ,它們互不重複,恰好是圖的六條邊;首尾均為 。重複經過 是容許的,因為定義禁止重複的是邊而非頂點。
總結
對至少有一條邊的有限圖,檢查連通性時忽略孤立頂點。剩餘頂點度數全為偶數時有閉歐拉跡;恰有兩個奇數度頂點時有以它們為端點的開放跡。重複頂點的跡仍可能是歐拉跡,重複邊則違反定義。奇偶判別法證明存在,邊序列提供可核查的路線;哈密頓圈則是不同的頂點條件。
這些判別法適用於上述有限無向圖;有向圖需要另行檢查入度和出度條件。