動機
單程道路只能按一個方向行駛。若把它當作無向邊,就可能錯誤地以為可以原路返回。有向圖明確表達這種不對稱。我們先區分兩種常見的連通性,再證明何時能沿每條有向邊恰走一次並返回起點。
定義
定義 5.1.1
(有向圖、遊走與連通性)
有限有向圖有有限頂點集 和有限有序邊集,邊 稱為弧。本節排除自環和重弧,但容許不同頂點之間兩個相反方向的弧。出度 計算離開 的弧數,入度 計算進入 的弧數。
有向遊走沿每條弧的指定方向前進;有向路徑是不重複頂點的有向遊走。有向跡不重複弧。長度為零的路徑使頂點可達自身。若每個頂點都能到達其他每個頂點,圖稱為強連通;若忽略方向後得到的無向圖連通,則稱為弱連通。強連通蘊含弱連通,反之不然,例如只有一條弧 的圖。
定義 5.1.2
(有向歐拉(Euler)迴路)
有向歐拉迴路是恰好使用每條弧一次的閉有向跡。入度和出度之和為零的頂點稱為孤立頂點。與無向情形相同,只檢查有弧關聯的頂點之間的連通性。若圖至少有一個頂點而沒有弧,我們容許長度為零的迴路;下述主要判別法假設至少有一條弧。
定理/命題
定理 5.1.3
(有向歐拉迴路判別法)
至少有一條弧的有限有向圖存在有向歐拉迴路,當且僅當每個頂點滿足 ,且所有關聯弧的頂點屬於同一個弱連通分支。
定理 5.1.4
(平衡使弱連通變為強連通)
若有限有向圖每個頂點入度等於出度,且非孤立頂點弱連通,則這些頂點強連通。
證明思路
證明
(進入與離開配對,再拼接閉跡)
必要性:閉有向跡在每個頂點把每次進入與下一次離開配對;起點的最後進入與最初離開配對。若恰好使用所有弧,入度等於出度。忽略迴路的方向得到一條經過所有弧端點的遊走,因此非孤立頂點弱連通。
充分性:從非孤立頂點出發,沿未用的出弧前進,直到沒有可用出弧。所得跡必定終止於起點。因為在其他頂點,若跡當前終止於此,已用入弧比已用出弧多一;原來的入度等於出度,故必有未用出弧。所以不可能停在不同於起點的頂點。
若還有未用弧,暫時刪去當前閉跡的弧。閉跡在每個頂點刪去相同數量的入弧和出弧,故剩餘有向圖仍平衡。當前跡上存在與未用弧關聯的頂點:從跡沿一條弱路徑走到某條未用弧的端點。如果路徑中有未用弧,第一條未用弧的前一端點在跡上,因為此前的弧都在跡上;如果路徑全由跡上的弧組成,其終點就在跡上,並與最初選定的未用弧關聯。剩餘弧的平衡性說明剩餘入度為正當且僅當剩餘出度為正。因此可從該點沿未用出弧走出另一條跡;同樣的論證說明它閉合。把新跡拼入原跡,每次至少消耗一條新弧,有限次後使用全部弧。
證明透視
剩餘平衡如何容許拼接
平衡在兩個不同地方被使用。在「走到無路可走」一步,它用於當前終點:起點以外的頂點進入的次數比離開多一次,原來的入度等於出度,故仍有未用的出弧。只有起點能吸收最後一次進入,因為它的第一次離開沒有對應的進入。在拼接一步,平衡用於剩餘圖:刪去一條閉跡會在每個頂點刪去同樣多的入弧和出弧,所以剩餘的弧仍平衡,同一論證再產生一條閉跡。
弱連通只用來找出新閉跡與舊閉跡相接的頂點;它從不提供方向,正是剩餘平衡把「與未用弧關聯」變成「有未用出弧」。每次拼接至少使用一條新弧,所以過程會終止。沒有弱連通,拼接點未必存在,例如兩個互不相連的三角形;沒有平衡,第一條跡可能停在起點以外,例如 。
證明
(從迴路讀出有向路徑)
第二個定理隨之得到:經過所有非孤立頂點的歐拉迴路中,從任一頂點到另一頂點都有一段有向遊走;刪除重複段可得到有向路徑。孤立頂點不包括在結論中,因為它不能到達其他頂點。
例題詳解
例題 5.1.5
(有向三角形)
弧 、、 使每個頂點各有一條入弧和出弧。路線 是有向歐拉迴路。在此例中它也是有向哈密頓(Hamilton)圈,但兩者的定義要求不同。
例題 5.1.6
(弱連通但不能返回)
對 ,忽略方向後的圖連通,但 不能到達 。兩端也不平衡: 出度 1、入度 0, 則相反。不存在使用兩條弧的閉有向跡。
例題 5.1.7
(平衡但不連通)
取兩個互不相連的有向三角形。每個頂點都平衡,但非孤立頂點屬於兩個弱連通分支。沒有單條有向跡能夠使用兩個分支的弧,因此只有平衡而無連通條件不夠。
常見錯誤
常見錯誤
(把弱連通當作可以雙向通行)
弱連通忽略箭頭方向,一般不能推出雙向可達。在 上,底層圖連通,但 不能到達任何頂點。上面推得強連通依賴每個頂點的度數平衡。
常見錯誤
(只檢查總數平衡而非逐點平衡)
總入度等於總出度在任意有限有向圖中自動成立,因為每條弧對兩個總數各貢獻一。它不能推出每個頂點各自平衡,而判別法要求的正是逐點平衡。
常見錯誤
(混淆歐拉迴路與哈密頓圈)
歐拉迴路關注弧,哈密頓圈關注頂點。迴路可在使用不同弧時重複經過頂點。兩個有向三角形僅共享一個頂點時,有經過兩個三角形的歐拉迴路,卻沒有哈密頓圈:刪去共享頂點後,底層無向圖不連通。
反例模式
強連通不能代替平衡
聲稱:強連通有向圖必有有向歐拉迴路,因為每條弧都可以到達,也可以離開。取弧 、、 與 。圈 使圖強連通。但 、,而 、。使用全部四條弧的閉跡要離開 兩次卻只進入一次,這不可能。事實上跡 用盡所有弧後停在 ,而 唯一的出弧已被用去。判別法要求每個頂點平衡;強連通是平衡加弱連通的推論,而不是平衡的替代品。
總結
平衡是逐點的局部條件,非孤立子圖弱連通是全局條件。兩者合起來給出使用所有弧的閉路線,進而得到非孤立頂點之間的強連通;沒有平衡時,弱連通與強連通不同。
練習
快速檢查
(圖含 、,另有孤立頂點 。按上述約定,它有有向歐拉迴路嗎?)
判斷連通條件涉及哪些頂點。
解答 · 答案
有。跡 使用兩條弧。孤立頂點沒有待經過的弧,不計入連通性檢查。
快速檢查
(圖含 、、。指出一個失敗的歐拉條件。)
計算每個頂點的入度和出度。
解答 · 答案
的出度為 、入度為 ,平衡失敗。所以圖沒有有向歐拉迴路,即使非孤立底層無向圖連通。
頂點集邊界上的度數平衡
對 ,以 記從 指向其補集的弧數,以 記從補集進入 的弧數。
引理 5.1.8
(邊界平衡恆等式)
在任意有限有向圖中,對每個 ,
特別地,若每個頂點平衡,則對每個 都有 。
證明
( 內部的弧互相抵消)
對 中各頂點 求 之和,並按端點位置把弧分類。兩端均在 內的弧在尾端貢獻 、在頭端貢獻 ,互相抵消。離開 的弧只在尾端貢獻 ,進入 的弧只在頭端貢獻 ,兩端都不在 的弧沒有貢獻。所以總和為 。
若每個頂點平衡,則每個頂點集的進入弧數與離開弧數相等。這解釋了平衡有向圖為何不能在兩個組之間有單向瓶頸。但這一恆等式本身不能排除互不連通的組,因此仍需要弱連通假設。
有限有向圖中,要求兩個頂點互相可達得到一個等價關係,其等價類稱為強連通分支。把每個強連通分支收縮成一個頂點,並保留不同分支之間的弧,所得縮點圖是有向無圈圖:若不同分支形成有向圈,圈上各分支將互相可達,本應屬於同一分支。
這給出「平衡加弱連通蘊含非孤立頂點強連通」的另一證明。
證明
(經縮點圖的第二個證明)
先限制在非孤立頂點誘導的子圖;它仍然平衡,且依假設弱連通。對該子圖縮點,假設所得縮點圖有不止一個頂點。有限有向無圈圖必有源點:從任一頂點反覆沿入弧向前追溯;有限且沒有有向圈,所以最終停在沒有入弧的頂點。在有不止一個頂點的弱連通縮點圖中,該源點必須有出弧。令 為其對應的原圖頂點集,則 、,與邊界平衡矛盾。所以非孤立頂點只有一個強連通分支。
此證明沒有假定弱路徑有一致方向。它僅在縮點後用弱連通保證所選源點至少關聯一條弧,再用平衡排除這些弧全向外的可能。若本來只有一個非孤立強分支,結論已經成立;沒有弧的圖不在該非孤立連通結論的範圍內。
快速檢查
(平衡有向圖中,若恰有三條弧離開頂點集 ,有多少條弧進入 ?)
應用邊界平衡恆等式。
解答 · 答案
邊界平衡恆等式給出 。兩端都在 的弧不影響此計數。
可達性與矩陣
將頂點編號為 。定義鄰接矩陣 :存在弧 時 ,否則為零。
命題 5.1.9
(鄰接矩陣的冪計算遊走數)
按這個行到列的約定,對每個非負整數 , 等於從 到 的長度 有向遊走數; 計算長度零遊走。
證明
(對遊走長度作歸納)
時,從 到 的長度零遊走存在當且僅當 ,與 相符。設命題對 成立,則
每條從 到 、長度為 的遊走,都唯一地分拆為從 到其倒數第二個頂點 的長度 遊走,再接上弧 。對應 的項恰好計算這些遊走,所以總和計算了全部遊走。
例如有向三角形 有
計算遊走 ;,因為從 3 出發的兩步遊走終止於 2。矩陣計數的是遊走,不一定是路徑:較長遊走可以重複頂點或弧。如果有向遊走連接兩頂點,刪除重複頂點之間的段,便得到相同端點的有向路徑。
概念視角代數
可達性即矩陣和的正性
令 。路徑長度至多為 ,每條遊走都可縮短為路徑,而每條路徑都是遊走。因此 可由 到達當且僅當 ;不同頂點互相可達當且僅當 且 。圖強連通當且僅當 的每個元素都為正。關於路線是否存在的命題,變成了一個可計算的整數矩陣的符號條件。
矩陣元素是整數計數,不是模二算術:若兩條不同的兩步遊走連接 ,整數項為 2,但在 中為零,可能錯誤地暗示不可達。
快速檢查
(上面的有向三角形中,從 出發走四步終止於何處?)
每個頂點恰有一條出弧。
解答 · 答案
三步後返回 ,再走一步到 ,所以 。每一步只有一個選擇。
開放有向歐拉跡
定理 5.1.10
(有向歐拉跡判別法)
設有限有向圖至少有一條弧, 為頂點。存在從 到 、恰好使用每條弧一次的有向跡,當且僅當 、、其餘頂點都平衡,且非孤立頂點弱連通。
證明
(用輔助頂點把跡閉合)
設有向跡恰好使用每條弧一次,且起點 與終點 不同。在所有內部訪問處將進入與離開配對; 有一條未配對的出弧, 有一條未配對的入弧。因此
其餘頂點都平衡;沿跡忽略方向,可見非孤立頂點弱連通。這些條件加上非孤立頂點弱連通也充分。添加新輔助頂點 ,以及弧 、。擴充圖平衡且非孤立頂點仍弱連通,故存在有向歐拉迴路。把迴路旋轉到從 開始,再刪去首尾兩條弧,剩餘跡從 到 ,恰好使用每條原弧一次。使用新頂點避免 原已存在時產生重弧。
這時所有弧可分成最少若干條跡,條數等於出度盈餘的總和。
通往推廣的路徑
若許多頂點都不平衡會怎樣?
這時所有弧可分成最少若干條跡,條數等於出度盈餘的總和。
仍設非孤立頂點弱連通,並令 。一條開跡只在起點使 的計數加 ,在終點減 ,所以覆蓋所有弧至少需要 條弧不交的跡。反過來,把盈餘單位與虧缺單位配對,對每一對 加入一個新頂點 及弧 。擴大後的圖滿足迴路判別條件;刪去這 個新頂點,就把它的歐拉迴路切成恰好 條跡。
快速檢查
(弧為 、、、。是否存在使用全部弧的有向歐拉跡?若有,給出一條。)
找出不平衡的頂點。
解答 · 答案
平衡, 的出度多一, 的入度多一。非孤立底層圖連通。跡 從 出發、以 為終點,恰好使用四條弧。它不能是迴路,因為兩個端點不平衡。