Beyond the Void
BYVoid
圖的割點、橋與雙連通分支
本文正體字版由OpenCC轉換

[點連通度與邊連通度]

在一個無向連通圖中,如果有一個頂點集合,刪除這個頂點集合,以及這個集合中所有頂點相關聯的邊以後,原圖變成多個連通塊,就稱這個點集爲割點集合。一個圖的點連通度的定義爲,最小割點集合中的頂點數。

類似的,如果有一個邊集合,刪除這個邊集合以後,原圖變成多個連通塊,就稱這個點集爲割邊集合。一個圖的邊連通度的定義爲,最小割邊集合中的邊數。

[雙連通圖、割點與橋]

如果一個無向連通圖的點連通度大於1,則稱該圖是點雙連通的(point biconnected),簡稱雙連通重連通。一個圖有割點,當且僅當這個圖的點連通度爲1,則割點集合的唯一元素被稱爲割點(cut point),又叫關節點(articulation point)

如果一個無向連通圖的邊連通度大於1,則稱該圖是邊雙連通的(edge biconnected),簡稱雙連通或重連通。一個圖有橋,當且僅當這個圖的邊連通度爲1,則割邊集合的唯一元素被稱爲橋(bridge),又叫關節邊(articulation edge)。

可以看出,點雙連通與邊雙連通都可以簡稱爲雙連通,它們之間是有着某種聯繫的,下文中提到的雙連通,均既可指點雙連通,又可指邊雙連通。

[雙連通分支]

在圖G的所有子圖G’中,如果G’是雙連通的,則稱G’爲雙連通子圖。如果一個雙連通子圖G’它不是任何一個雙連通子圖的真子集,則G’爲極大雙連通子圖雙連通分支(biconnected component),或重連通分支,就是圖的極大雙連通子圖。特殊的,點雙連通分支又叫做

[求割點與橋]

該算法是R.Tarjan發明的。對圖深度優先搜索,定義DFS(u)爲u在搜索樹(以下簡稱爲樹)中被遍歷到的次序號。定義Low(u)爲u或u的子樹中能通過非父子邊追溯到的最早的節點,即DFS序號最小的節點。根據定義,則有:

Low(u)=Min { DFS(u) DFS(v) (u,v)爲後向邊(返祖邊) 等價於 DFS(v)<DFS(u)且v不爲u的父親節點 Low(v) (u,v)爲樹枝邊(父子邊) }

一個頂點u是割點,當且僅當滿足(1)或(2) (1) u爲樹根,且u有多於一個子樹。 (2) u不爲樹根,且滿足存在(u,v)爲樹枝邊(或稱父子邊,即u爲v在搜索樹中的父親),使得DFS(u)<=Low(v)。

一條無向邊(u,v)是橋,當且僅當(u,v)爲樹枝邊,且滿足DFS(u)<Low(v)。

[求雙連通分支]

下面要分開討論點雙連通分支與邊雙連通分支的求法。

對於點雙連通分支,實際上在求割點的過程中就能順便把每個點雙連通分支求出。建立一個棧,存儲當前雙連通分支,在搜索圖時,每找到一條樹枝邊或後向邊(非橫叉邊),就把這條邊加入棧中。如果遇到某時滿足DFS(u)<=Low(v),說明u是一個割點,同時把邊從棧頂一個個取出,直到遇到了邊(u,v),取出的這些邊與其關聯的點,組成一個點雙連通分支。割點可以屬於多個點雙連通分支,其餘點和每條邊只屬於且屬於一個點雙連通分支。

對於邊雙連通分支,求法更爲簡單。只需在求出所有的橋以後,把橋邊刪除,原圖變成了多個連通塊,則每個連通塊就是一個邊雙連通分支。橋不屬於任何一個邊雙連通分支,其餘的邊和每個頂點都屬於且只屬於一個邊雙連通分支。

[構造雙連通圖]

一個有橋的連通圖,如何把它通過加邊變成邊雙連通圖?方法爲首先求出所有的橋,然後刪除這些橋邊,剩下的每個連通塊都是一個雙連通子圖。把每個雙連通子圖收縮爲一個頂點,再把橋邊加回來,最後的這個圖一定是一棵樹,邊連通度爲1。

統計出樹中度爲1的節點的個數,即爲葉節點的個數,記爲leaf。則至少在樹上添加(leaf+1)/2條邊,就能使樹達到邊二連通,所以至少添加的邊數就是(leaf+1)/2。具體方法爲,首先把兩個最近公共祖先最遠的兩個葉節點之間連接一條邊,這樣可以把這兩個點到祖先的路徑上所有點收縮到一起,因爲一個形成的環一定是雙連通的。然後再找兩個最近公共祖先最遠的兩個葉節點,這樣一對一對找完,恰好是(leaf+1)/2次,把所有點收縮到了一起。

[圖的雙連通性問題例題]

備用交換機 求圖的割點,直接輸出。

pku 3177(3352) Redundant Paths 求橋,收縮邊雙連通子圖,構造邊雙連通圖。

POI 1999 倉庫管理員 Store-keeper 求點雙連通子圖。

BYVoid 原創講解,轉載請註明。


上次修改時間 2017-05-22

相關日誌