頂點可以重訪,邊不能重用
假設要恰好檢查每一段道路一次。經過同一個路口多次可以,但不能重複經過同一道路。區分頂點和邊十分重要:歐拉(Euler)迴路可以多次經過一個頂點,因而不必是通常意義下的簡單圈。
以下 是至少有一個頂點的有限無向多重圖。平行邊是不同的邊;允許自環,且一個自環對其頂點的度數貢獻二。
定義 2.2.1
(跡、歐拉跡與歐拉迴路)
跡是沒有重複邊的遊走;歐拉跡恰好使用每條邊一次。起點和終點不同時稱為開放歐拉跡;起終點相同的歐拉跡稱為歐拉迴路。正度數頂點稱為非孤立頂點,零度的孤立頂點不需要由正長度跡訪問。
對於沒有邊的圖,約定任取一個頂點處長度為零的遊走是歐拉迴路;不存在開放歐拉跡。以下判據單獨討論至少有一條邊的情形,因而非孤立頂點集合非空。
定理 2.2.2
(歐拉迴路判據)
設 至少有一條邊。存在歐拉迴路,當且僅當所有非孤立頂點屬於同一連通分支,且每個頂點的度數都是偶數。
定理 2.2.3
(開放歐拉跡判據)
設 至少有一條邊。存在開放歐拉跡,當且僅當所有非孤立頂點屬於同一連通分支,且恰有兩個奇度頂點;這兩個頂點就是開放跡的端點。
為甚麼度數必須滿足奇偶條件?
證明
(把進入和離開配對)
跡經過一個頂點時,將進入所用的關聯次數與離開所用的關聯次數配對。自環在該頂點有兩次關聯,一次用於離開、一次用於進入,故對度數貢獻二。閉跡在起點也能配對所有進入與離開,因此若閉跡恰用每條邊一次,各頂點的度數均為偶數。
開放跡從 到 時,除 的首次離開和 的最後進入外,其他關聯次數均可配對。因此 為奇度頂點,其餘頂點度數為偶數。此外每條邊的端點都出現在這條跡上,所以非孤立頂點在同一連通分支。以上只證明必要性,還沒有構造所需的跡。
度數全偶時,拼接閉跡
證明
(延長並拼接閉跡)
假設非孤立頂點連通且所有度數為偶數。從任一非孤立頂點 出發,只沿未用過的邊前進;只有當前頂點沒有未用關聯邊時才停止。圖的邊數有限,過程必停止。
它不可能停在不同於 的頂點:在這樣的頂點,一次到達後、離開之前,已用的關聯次數為奇數;總度數為偶數,所以還存在未用的關聯次數。自環按兩次關聯計數並作為整條邊使用,不改變奇偶論證。因此這條不能繼續延長的跡回到 ,是一條閉跡。
若它已用完所有邊,便得到歐拉迴路。否則暫時移去已用邊。閉跡在每個頂點用掉偶數次關聯,因此剩餘圖各頂點的度數仍為偶數。原圖的非孤立部分連通,所以原閉跡上必有頂點與未用邊相接:從閉跡出發沿原圖走向一條未用邊,取路徑上第一條尚未使用的邊,其起點就在閉跡上。
從這個共同頂點沿剩餘未用邊再次行走直到不能繼續;同一奇偶論證給出另一條閉跡。將新閉跡拼入舊跡:沿舊跡走到共同頂點,走完新閉跡回到該點,再繼續舊跡。所得跡仍閉合且不重複邊。每次拼接至少使用一條先前未用邊,而邊數有限,因此過程最終用盡所有邊。這同時證明迴路存在並給出構造方法。
證明透視
每個假設在哪裏用上
每個假設都在一個可以指明的位置用上。偶數度數用了兩次,形式相同。起點以外的頂點一旦被進入,已用的關聯次數為奇數,因此還有未用的關聯,這迫使每條不能延長的遊走回到起點閉合。一條閉跡在每個頂點用掉偶數次關聯,所以剩餘圖的度數仍全為偶數,同一論證可以在其上再次進行。非孤立頂點的連通性在每次拼接時用一次,只用來保證當前閉跡碰到某條未用邊;缺少它,構造會在另一個分支仍有邊時停止,如下面兩個互不相連的三角形。有限性兩次給出終止:每次行走會停止,而每次拼接至少用掉一條新邊。論證不依賴起點,也不依賴選取哪條未用邊,所以這是一個構造方法,而不是搜尋。
例題 2.2.4
(把兩個三角形拼起來)
取頂點 ,邊為 。兩個三角形只共享頂點 。有 ,其餘頂點度數均為 2。先走閉跡 ,再在 處拼入未用閉跡 ,得到
這條遊走恰用六條邊各一次。它重複經過 ,但沒有重複邊,因此是歐拉迴路,儘管不是簡單圈。
例題 2.2.5
(拼入一個自環)
設 的頂點為 ,邊為 ,並在 處有自環 。則 ,,全為偶數,且圖連通。從 出發走 ;回到 時它的兩次關聯都已用完,遊走如證明所預言般停在起點。自環尚未使用,並在 處與這條跡相接。把閉跡 在 處拼入,得到 ,恰用四條邊各一次。若自環只算一次, 的度數看似是奇數 ,判據便會錯誤地否定迴路的存在。
恰有兩個奇度頂點時
證明
(添加一條有標記的臨時邊)
假設非孤立部分連通,恰有 兩個奇度頂點。添加一條連接 的新臨時邊;即使原圖已有這兩個頂點之間的邊,也把新邊作為另一條不同的邊。現在 的度數變偶,其餘度數不變,圖仍連通。根據迴路判據,擴充後的圖有一條使用全部邊的歐拉迴路。
從迴路的循環表示中選取起點,使臨時邊成為最後一條邊,再刪去它。剩下的遊走恰用原圖每條邊一次,端點分別是 ,因此是開放歐拉跡。在多重圖中必須標記臨時邊,以免與已有平行邊混淆。
例題 2.2.6
(連接兩個奇度頂點的開放跡)
在上述兩個三角形的圖中,給原圖增加一條邊 ,則只有 度數為奇數。一條從 到 的跡是
它依次使用 ,每條恰一次。這裏 是題目圖中的一條原邊;證明中添加的臨時邊則是另外一條需要標記的邊。
反例模式
僅有偶度不足以連接不同部分
兩個互不相連的三角形中,每個頂點度數都是 2,但沒有一條遊走能夠使用兩個分支的所有邊。有歐拉迴路的圖可以有孤立頂點,因為它們沒有需要覆蓋的邊;卻不能有兩個各自含邊的連通分支。故連通條件只針對非孤立頂點。
常見錯誤
(走到卡住得到的是閉跡,未必用完所有邊)
當所有度數為偶數時,沿未用邊走到不能繼續,必定回到起點,但不一定用完每條邊。在兩個三角形的圖中,遊走 停在 ,而 仍未使用。拼接步驟是構造的一部分,不是可有可無的改良。
常見錯誤
(自環要算兩次)
自環對其頂點的度數貢獻二。在下面第一題中,若把 處的自環只算一次,會得到 、,即只有一個奇度頂點,而這在任何圖中都不可能。正確的計數 表明歐拉迴路存在。
練習與解答
快速檢查
(設 的頂點為 , 之間有兩條不同邊 , 處有自環 。判斷 是否有歐拉迴路;若有,給出一條。)
解答 · 答案
自環貢獻二,故 、。非孤立部分連通,因此有歐拉迴路,例如 。標記邊以區分兩條平行邊。
快速檢查
(對路徑 ,判斷是否存在歐拉迴路或開放歐拉跡。)
解答 · 答案
對 ,度數依次為 。非孤立部分連通,恰有奇度端點 ,因此有開放歐拉跡,圖中顯示的路徑就是一條。由於有奇度頂點,不存在歐拉迴路。
快速檢查
( 有歐拉迴路或開放歐拉跡嗎?)
解答 · 答案
在 中每個頂點度數為 3,共有四個奇度頂點。儘管圖連通,它既沒有歐拉迴路,也沒有開放歐拉跡。兩個奇度頂點的條件必須恰好滿足。
應用判據時,先明確有無自環和平行邊,自環按二計算;再忽略孤立頂點檢查連通性,最後看度數的奇偶性。