學習提示: 本頁包含各道練習的完整解答;請先自行嘗試,再展開解答。
刪除一條連接與刪除一個交匯點,是不同的失效。環能提供避開某條邊的替代路徑,但所有路線仍可能經過特定頂點。因此不能原封不動地把橋的判準用來找割點。
我們不只給出是或否,而是計算刪除各頂點後剩下多少連通分量。數目本身揭示證明:某些 DFS 子樹獨立成塊,其餘則連到被刪頂點上方的部分。DFS 根上方沒有任何部分,所以公式必須不同。
這裏的刪除都是從同一原圖出發、各自假設的一次刪點。我們不是先刪一個頂點、更新圖,再刪另一個。方法靜態分析全部可能的單頂點失效。
精確說明刪掉甚麼
設 是頂點為 的有限無向圖,容許 、自環及平行邊。刪除 是移除頂點及全部相鄰邊。 時,餘圖有 個頂點;空圖的連通分量數為零。
定義 10.3.1
(以連通分量數增加定義割點)
令 為原圖連通分量數。對每個頂點 ,令 為 的分量數。 是割點,當且僅當
刪除孤立頂點會令數目減一,因此它不是割點。若原圖只有一個頂點,刪掉後剩零個分量。
只有原本包含 的分量會分裂或消失,其餘 個分量不變。我們要計算多少新部分取代這一個原分量。
概念視角結構
分隔就是路線必須經過 v
等價地, 是割點,當且僅當存在兩個異於 的頂點 ,它們在 中連通,卻每條連接兩者的路線都經過 。這時 和 落在 的不同分量。分量數 則說明這類頂點對共落在多少塊之中。
哪些 DFS 子樹可不經父頂點逃出?
執行 DFS 森林,為各頂點記錄發現時間 及 DFS 父頂點。樹子頂點是直接從目前頂點首次發現的頂點,不是所有發現時間較大的相鄰頂點。
頂點 完成時, 是從 出發,沿零條或多條 DFS 樹邊向下,再沿至多一條非樹邊到祖先,可到達的最早發現時間;容許完全不移動。初始化為 。已完成子頂點提供其 low 值,連到已發現端點的非樹邊則提供該端點的發現時間。已發現的後代具有較晚發現時間,不會降低一個已不大於目前頂點自身發現時間的值。
無向圖有兩個重要結構性質。非樹邊連接祖先與後代,自環視為退化情況。同一頂點不同 DFS 子樹之間亦沒有直接連邊:先探索的子樹若檢查到這種邊,就會在返回前發現另一端,把它納入同一子樹。
定理 10.3.2
(非根頂點的分離子頂點判定)
設 為非根頂點, 為 的樹子頂點。刪去 後, 的子樹與 上方部分相連,當且僅當 ;它成為獨立的分量,當且僅當
若只返回 ,當 自己被刪時就沒有幫助,所以分離條件是非嚴格的。
證明透視
每個符合條件的子頂點產生一個獨立分量
刪除 後, 子樹內的 DFS 樹邊仍令其中全部頂點連通。任何離開該子樹的邊,必須通往 或祖先,因為不相關子樹沒有連邊。若 ,就沒有邊到達 的嚴格祖先。因此刪除 令整個子樹與其餘部分分開,成為一個分量。
若 ,則子樹有逃出邊到嚴格祖先。把子樹內的樹路徑與此邊結合,就能不經 連到其上方部分。
非根 的父側部分非空,而且可由剩餘 DFS 樹邊連通。全部不分離的子樹都併入它。每個分離子樹另加一個分量,亦不能與其他子樹合併。所以若 個子頂點符合非嚴格條件,原分量恰好變成 個分量。
反例模式
等號可以保護邊,卻不能保護被刪端點
取頂點 0、1、2,一條邊 及兩條平行邊 。由 0 開始 DFS,2 是 1 的子頂點。第二條平行邊回到 1,所以 。
兩條 都不是橋,刪掉其中一條仍有另一條。但刪除頂點 1 會同時移除兩條及 ,令 0 與 2 分開,所以 1 是割點。嚴格的橋條件 會漏掉它。回到將被刪除的頂點,不是一條存活的逃出路線。
根只有子樹部分,沒有父側部分
設 DFS 根 有 個樹子頂點。刪除 後,各子樹仍各自連通,但不同子樹不能互連。這 個子樹已涵蓋原分量內除 以外的全部頂點。
證明透視
根公式只計算真正存在的部分
根沒有父側分量。刪除後,原分量恰好成為 個分量。這包括 :根原本是孤立頂點,其分量完全消失。回到根的邊也隨根刪掉,事後不能用來連接子樹。
所以根是割點,當且僅當 。只有一個子頂點的根,即使有很多相鄰邊,也不是割點,因為這些邊可能全都進入同一 DFS 子樹。
把局部分裂與其餘不變的 個分量合併,得到完整刪點數:
定理 10.3.3
(刪點後的分量數)
對 的每個頂點 ,設 為 的連通分量數,
其中 是 的 DFS 樹子頂點數, 是滿足 的樹子頂點 的個數。
非根的判準是 ,根的判準是 。兩者都由同一分量數定義推出,不是兩條互不相關、只能背誦的例外。
反例模式
非根公式會替根虛構父側分量
根只有一個樹子頂點時,其原分量內只剩一個部分。根的全部子頂點都符合低連結判定,因為同一 DFS 樹內不可能有早於根的祖先。若直接用 ,便答成 ;正確結果卻是 。
孤立根也一樣,錯誤公式給 ,正確值則為 。缺少父側部分正是根計算不同的原因;改查根的度數,並不能解決這個問題。
常見錯誤
(忘記不變的分量)
公式 保留其餘 個原有分量。對有 個分量的圖中的孤立根,若寫成 ,就是聲稱沒有分量剩下。正確的值是 ,正如七個頂點的例子:刪去頂點 6 後剩下一個分量。
在非連通例子計算失效
例題 10.3.4
(兩個割點與一個孤立點造成不同效果)
取 ,邊依以下次序輸入:
首五個頂點組成兩個共享頂點 2 的三角形,5 接在 4 上,6 則孤立。初始 。外層按編號遞增考慮根,鄰接項保留插入次序時,第一棵 DFS 樹是鏈 ,6 是另一個根。
| 頂點 | DFS 父頂點 | 發現時間 | Low 值 | 刪除後分量數 |
|---|---|---|---|---|
| 0 | 無 | 0 | 0 | 2 |
| 1 | 0 | 1 | 0 | 2 |
| 2 | 1 | 2 | 0 | 3 |
| 3 | 2 | 3 | 2 | 2 |
| 4 | 3 | 4 | 2 | 3 |
| 5 | 4 | 5 | 5 | 2 |
| 6 | 無 | 6 | 6 | 1 |
頂點 2 有分離子頂點 3,因為 。刪除後剩 、 及 。頂點 4 有分離子頂點 5,刪除後剩 、 及 。這兩個頂點就是割點。
根 0 只有一個 DFS 子頂點,刪除後數目仍為 2。刪除孤立根 6 則移除整個分量,令數目降至 1。傳回的刪點數陣列為 。
在多重圖實作保留低連結含義
每個輸入邊實例各有獨立編號,兩個鄰接端點都儲存同一編號。探索頂點時,只跳過通往父頂點所用的那一條邊。另一條平行邊仍是非樹邊,可以提供父頂點的發現時間。自環不影響最小值,也不增加樹子頂點數。
複製一條邊不會改變刪點後的劃分,因為沒有新增可達頂點對。不過,邊身分對這裏證明的精確 low 值仍有必要,也令表示方式與橋這類對邊敏感的應用一致。不要從平行邊例子誤推邊的重數本身會產生新割點。
常見錯誤
(按頂點而不是按邊 ID 跳過父頂點)
若 DFS 跳過所有通向父頂點的邊,而不是只跳過到達時所用的那一條,樹邊的平行副本就會被忽略。在邊 加上兩條 的例子中,這會令 ,而不是 。這裏割點的答案不變,因為兩個值都滿足 ,但儲存的 low 值是錯的,以它為基礎的橋判定會把 當成橋,儘管仍有平行副本。
明確 DFS 堆疊儲存頂點及下一鄰接索引。發現新頂點時,增加父頂點的樹子數。子框架完成時,將其最終 low 值傳給父頂點一次,非嚴格判定則增加父頂點的分離子數。根也可能累積此分離數,但最後答案改用它的樹子數。
以下函數假設 為整數,各邊是含兩個整數端點的配對。它拒絕負 及範圍外端點,只讀邊而不修改調用者串列。結果為 (original_count, deletion_counts, articulation_vertices),最後一項的頂點標籤按遞增次序排列。
def vertex_deletion_components(n, edges):
if n < 0:
raise ValueError("the vertex count must be nonnegative")
graph = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
if not (0 <= u < n and 0 <= v < n):
raise ValueError("edge endpoint outside the vertex range")
graph[u].append((v, edge_id))
graph[v].append((u, edge_id))
tin = [-1] * n
low = [0] * n
parent = [-1] * n
parent_edge = [-1] * n
children = [0] * n
separating = [0] * n
timer = 0
original_count = 0
for root in range(n):
if tin[root] != -1:
continue
original_count += 1
tin[root] = low[root] = timer
timer += 1
stack = [(root, 0)]
while stack:
vertex, index = stack[-1]
if index < len(graph[vertex]):
neighbor, edge_id = graph[vertex][index]
stack[-1] = (vertex, index + 1)
if edge_id == parent_edge[vertex]:
continue
if tin[neighbor] == -1:
parent[neighbor] = vertex
parent_edge[neighbor] = edge_id
children[vertex] += 1
tin[neighbor] = low[neighbor] = timer
timer += 1
stack.append((neighbor, 0))
else:
low[vertex] = min(low[vertex], tin[neighbor])
else:
stack.pop()
predecessor = parent[vertex]
if predecessor != -1:
low[predecessor] = min(low[predecessor], low[vertex])
if low[vertex] >= tin[predecessor]:
separating[predecessor] += 1
deletion_counts = [
original_count - 1 + children[v]
if parent[v] == -1 else original_count + separating[v]
for v in range(n)
]
articulation_vertices = [
v for v in range(n) if deletion_counts[v] > original_count
]
return original_count, deletion_counts, articulation_vertices
全部 DFS 森林探索完後,才使用全局分量數。 且沒有邊時,結果為 (0, [], []),沒有頂點需要考慮刪除。負端點標籤會先被拒絕,不讓 Python 把它解作從尾部開始的索引。
例題 10.3.5
(根在圖中的度數,不決定其 DFS 子頂點數)
星形圖有邊 、、,根為 0。每個葉都開啟新子樹,刪除 0 後剩三個分量,所以它是割點。刪除任一葉則剩一個分量。
三角形 若由 0 經 1 探索,2 會從 1 被發現。根 0 度數為二,卻只有一個樹子頂點。刪除後仍有邊 ,因此只剩一個連通分量。另一相鄰頂點是後代,而非第二個樹子頂點。應計算直接由根發現的次數,不是全部鄰居數。
例題 10.3.6
(路徑上的自環不改變結果)
取 及邊 。自環使頂點 0 多兩個邊端,兩者都檢查已被發現的頂點 0,所以 。DFS 樹是鏈 ,。頂點 2 有 ,所以頂點 1 有一個分離子頂點,。頂點 0 是有一個樹子頂點的根,所以 。頂點 2 不是根且沒有子頂點,所以 。函數返回 (1, [1, 2, 1], [1]):只有頂點 1 是割點,自環不起作用。
複雜度與結論的限制
若輸入有 個邊實例,鄰接表示有 個項目,自環也存兩次。每頂點發現一次,每鄰接項檢查一次,每個完成的子頂點做常數返回工作。因此建立、遍歷及輸出共需 時間,及 額外儲存單元,不受遞歸深度限制。這是普通圖操作界,不是任意大整數標籤的位元複雜度界。
最終刪點數及割點集合不依賴 DFS 根或邊次序,但發現時間、low 值及父項陣列可不同。它們也不回答同時刪除兩個頂點的問題:另一個被刪頂點可能破壞證明所用的逃出路徑,所以不能直接合併單次失效答案。
論證針對無向連通性。有向強連通需要不同分析;這裏使用的「不相關 DFS 子樹沒有連邊」,不是任意有向 DFS 的性質。應把失效對象、圖類型及低連結值含義,一併保留在定理中。
練習與完整解答
快速檢查
(1. 連通圖的非根頂點 v 有三個 DFS 子頂點,low 值為 2、5、7,而 tin[v]=5。刪除後有多少分量?v 是否割點?)
解答 · 1. 等號也算分離子頂點
Low 值 5 及 7 的兩個子頂點符合條件,所以 ;值為 2 的子樹會接到父側分量。由 ,總數是 ,大於原本數目,故 是割點。只計嚴格不等式,會錯漏只返回 的子樹。
快速檢查
(2. 圖有 c=4 個分量。DFS 根分別有零、一、三個樹子頂點時,D(r) 各是多少?哪些是割點?)
解答 · 2. 恰好替換一個原分量
用 ,依次得到 、、。只有三個子頂點的根增加數目,是割點。零子頂點表示孤立根,其整個分量消失;一個子頂點則留下一個替代分量。
快速檢查
(3. 七頂點例子中,分別列出刪除 2 及刪除 6 後的分量。為何這是兩個獨立的假設結果?)
解答 · 3. 保留其餘原分量
刪除 2 留下 、 及 ,數目為 3。從原圖刪除 6,則只剩分量 ,數目為 1。第二個答案並非從已刪除 2 的圖開始;每個陣列值都指原圖不變下,另一次單獨刪點。
快速檢查
(4. 有邊 0-1 及兩條 1-2 的圖中,為何 1 是割點,但任何一條 1-2 都不是橋?再增加重複邊會否改變刪點數?)
解答 · 4. 刪點同時移除全部平行副本
刪掉一條 後,端點間還有另一條路。刪除頂點 1 卻移除其全部相鄰邊,留下孤立 0 及 2,令分量數由一增至二。更多副本不改變刪點前後的可達頂點對,因此不改變這些數目。額外平行邊對精確 low 值 的計算仍有作用。
快速檢查
(5. 三角形中的 DFS 根有兩個鄰居,但只有一個樹子頂點,兩者有何分別?刪根後結果是甚麼?為何度數至少二不足以判根?)
解答 · 5. 後代鄰居不是新發現的子頂點
沿根的一條邊開始時,首個子頂點會在根檢查另一條邊之前,先發現第二個鄰居。兩鄰居都在同一子樹。刪根後仍有邊連接它們,所以剩一個分量,根不是割點。度數計算相鄰邊結構,根定理則計算分開的 DFS 子樹。
快速檢查
(6. 迭代實作為何要等子框架完成才傳遞 low[child]?若把初始發現時間當成最終 low 值,會出甚麼錯?)
解答 · 6. 後代逃出資訊在返回時才齊備
剛發現的子頂點只知道自身發現時間,後代之後可能找到通往祖先的非樹邊,降低正確值。若只傳最初值,可能錯判子樹分離。例如三角形 的非樹邊 2 到 0,會把 降至 0;若用初始 對父頂點 1 判定,便會錯認 1 是割點。明確框架的完成事件,保證父頂點作最後判定前,全部後代資訊已到齊。