甚麼是橋邊?
定義 3.1.1
(多重圖的橋邊)
在有限無向多重圖中,每條邊有不同 ID;允許平行邊及自環。若刪除某一條邊會增加連通分支數目,該邊便是橋邊。定義也適用於不連通的圖。
自環永遠不是橋邊;兩條平行邊中的任何一條也不是橋邊,因為刪去一條後,另一條仍連接相同端點。
深度優先搜尋(DFS)能在線性時間找出所有橋邊,但實作時必須分清進入頂點所用的邊與通往同一父頂點的其他邊。我們計算頂點及邊 ID,而不只計算端點對。
概念視角結構
橋就是不在任何圈上的邊
等價地,一條邊是橋,當且僅當它不在任何圈上。經過 的圈就是 加上連接其兩端、且避開 的一條路線;兩條平行邊構成長度為二的圈,自環則是長度為一的圈。low-link 測試就是為樹邊偵測這樣的圈。
發現時間與可達祖先
由每個仍未訪問的頂點啟動 DFS。把不同的正整數發現時間設為 ,並初始化 。對由 通往新訪問頂點 的樹邊,先完成 的遞歸搜尋,再令
對任何其他連到已訪問頂點 的入射邊,除了進入 所用的那一個邊 ID,令 。自環只會與 比較,不會降低值。連到已發現後代的邊也不會降低值,因為 。
定義 3.1.2
(Low-link 值)
從 返回後, 是如下方式可達的最小發現時間:在 的子樹內向下走零條或多條 DFS 樹邊,然後最多使用一條非樹邊到某個祖先(包括 本身)。
初始化容許不使用非樹邊。子節點更新傳遞其最小值,已訪問鄰點更新處理非樹邊。在無向 DFS 中,非樹邊連接祖先和後代,或是一個自環:否則,先被探索的端點會在完成前發現另一端,使其成為後代。
橋邊判準
定理 3.1.3
(Low-link 橋邊判準)
令 為橋邊集合。對 DFS 樹邊 ,其中 是 的父頂點,
每條非樹邊(包括每個自環)都不是橋邊。
證明
(返回路徑與唯一連接)
若 , 本身或其某個後代有一條非樹邊通往 或其祖先。沿零條或多條樹邊向下走至該邊端點、經非樹邊,再在需要時沿樹邊返回 ,便得到一條避開 的 至 路徑;刪去 不會斷開其端點。
反過來,設 。從 的子樹離開的每條非樹邊,都通往 的某個不同於 本身的祖先,即 或 的祖先;而任何這樣的邊都會給出 ,所以不存在這種邊。由 DFS 性質,也沒有邊從該子樹通往另一個已完成子樹。因此 是該子樹通往其 DFS 分支其餘部分的唯一邊,刪去它會增加分支數目。
非樹邊永遠不是橋邊:其端點已有樹路徑,或它是一個自環。
證明透視
嚴格不等式與進入邊的 ID
不平凡的步驟是逆向部分,它用到無向 DFS 的兩個性質:非樹邊連接祖先和後代,且已完成的不同子樹之間沒有邊。兩者合起來說明,離開 的子樹的邊只會向上通往祖先,所以 能看到所有這些邊。不等式必須是嚴格的:連回 本身的邊給出 ,那是一條替代路徑。父邊必須按其 ID 跳過,而不是按端點跳過:進入所用的那一條邊就是正在測試的樹邊,而它的平行副本則是真正的返回路徑。
平行邊說明為何必須跳過父邊,而不是跳過所有通向父頂點的邊。若 以一條邊進入 ,而另一條邊也連接兩者,第二個 ID 給出 。
反例模式
跳過所有通向父頂點的邊
一種誘人的實作會跳過所有另一端是父頂點的邊。取頂點 及連接兩者的兩條邊 和 。從 出發,,經邊 進入 ,故 。在 處,邊 因通向父頂點而被跳過,於是 ,邊 被報告為橋邊。其實並非如此:刪去邊 後仍有邊 ,圖依然連通。只跳過進入 所用的那一個 ID,則 ,得到正確答案:沒有橋邊。
DFS 追蹤例子
例題 3.1.4
(帶自環的六頂點多重圖)
取頂點 及下列邊 ID,鄰接表依 ID 遞增次序處理:
| ID | 端點 | ID | 端點 |
|---|---|---|---|
| 1 | 5 | ||
| 2 | 6 | ||
| 3 | 7 | ||
| 4 | 8 |
由 啟動 DFS,發現時間由 開始。樹按 的次序訪問。第二條 邊把 降至 ;邊 把 降至 ,並經 和 傳遞。 的自環不改變最小值。
| 頂點 | ||||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 1 | 2 | 2 | 2 | 6 |
只有邊 是橋邊,因為 。對樹邊 ,等式 正確地排除橋邊。
例題 3.1.5
(平行邊、自環與懸掛頂點)
取頂點 及邊 、、、。從 出發,,經邊 進入 ,故 。在 處跳過邊 (進入所用的 ID);邊 通向已訪問的 ,令 ;自環 只與 比較,不改變任何值;邊 進入 ,,而 的另一條邊只有進入邊,所以 。返回 後,。對邊 的測試 不成立;對邊 的測試 成立。所以只有邊 是橋邊,與逐條刪邊的結果一致。
例題 3.1.6
(樹與孤立頂點)
設邊為 和 ,另有第四個沒有邊的頂點 。從 啟動 DFS, 的 為 ,沒有非樹邊,所以 。於是 ,,兩條邊都是橋邊。DFS 還必須由仍未訪問的 啟動;它找不到樹邊,所以不增加橋邊。
常見錯誤
(用「大於或等於」代替「嚴格大於」)
測試 是割點的條件,不是橋邊的條件。在六頂點的追蹤中,它會把樹邊 標為橋邊,因為 ,但邊 提供了從 回到 的另一條路。橋邊的不等式必須是嚴格的。
常見錯誤
(只從一個頂點啟動 DFS)
對於由一條邊連接 、另一條邊連接 的兩個分支,從 啟動的 DFS 只會找到第一條橋邊。必須從每個仍未訪問的頂點啟動搜尋,因為橋邊的定義適用於每個分支。
成本
定理 3.1.7
(橋邊搜尋的線性時間)
使用鄰接表時,DFS 橋邊搜尋需要 時間,圖與陣列需要 空間;遞歸實作另可能需要 調用堆疊空間。
證明
(計算入射次數)
每個頂點被訪問一次,且每個頂點至多啟動一次搜尋。每條邊至多在其兩個端點的鄰接表中各出現一次(自環在同一頂點出現兩次),每次出現只以常數時間的比較或更新處理一次。總和為 。陣列 和 長度為 ,圖本身需要 空間;遞歸深度至多為 。
即使重排鄰接表,也應儲存及比較邊 ID:發現時間可能改變,橋邊集合則不變。
習題
快速檢查
(在六頂點例圖中先刪去邊 6,再執行 DFS。現在哪些邊是橋邊?不要只依賴舊的 low 值解釋。)
刪去後, 部分是甚麼形狀?
解答 · 答案
邊 3、4、5、7 是橋邊。此時 部分是一條路徑,刪去其中任何一邊都會斷開它。邊 1、2 仍然平行,並非橋邊;自環也不是橋邊。
快速檢查
(刪去 的自環後,其他邊的橋邊狀態如何改變?為甚麼?)
自環能否幫助連接兩個不同的頂點?
解答 · 答案
其他邊的狀態不變:自環不能連接不同頂點,也不能在兩者之間提供替代路徑。
快速檢查
(兩個頂點由三條不同平行邊連接。有多少橋邊?若 DFS 跳過所有指向父頂點的邊,可能出現甚麼錯誤?)
刪去一條邊,看看還剩下甚麼。
解答 · 答案
沒有橋邊。若跳過所有指向父頂點的邊,可能把另外兩條平行邊也丟掉,令樹邊看似沒有返回路徑。
快速檢查
(三角形的邊為 、、,依此邊次序由 啟動 DFS。給出 、 及橋邊。)
邊 是唯一的非樹邊。
解答 · 答案
樹為 ,。在 處,邊 通向 ,所以 ,傳遞後 、。測試 與 都不成立。沒有橋邊,這正是圈應有的結果。