[點連通度與邊連通度]

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

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

[雙連通圖、割點與橋]

如果一個無向連通圖的點連通度大於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 原創講解，轉載請註明。