[點(diǎn)連通度與邊連通度]

在一個(gè)無(wú)向連通圖中，如果有一個(gè)頂點(diǎn)集合，刪除這個(gè)頂點(diǎn)集合，以及這個(gè)集合中所有頂點(diǎn)相關(guān)聯(lián)的邊以后，原圖變成多個(gè)連通塊，就稱這個(gè)點(diǎn)集為割點(diǎn)集合。一個(gè)圖的點(diǎn)連通度的定義為，最小割點(diǎn)集合中的頂點(diǎn)數(shù)。

A cut, vertex cut, or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. Theconnectivity or vertex connectivity κ(G) is the size of a smallest vertex cut. A graph is called k-connected or k-vertex-connected if its vertex connectivity is k or greater. A complete graph with n vertices has no cuts at all, but by convention its connectivity is n-1. A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ(u,v) is the size of a smallest vertex cut separating u and v. Local connectivity is symmetric for undirected graphs; that is, κ(u,v)=κ(v,u). Moreover, except for complete graphs, κ(G) equals the minimum of κ(u,v) over all nonadjacent pairs of vertices u,v.

2-connectivity is also called "biconnectivity" and 3-connectivity is also called "triconnectivity".

Analogous concepts can be defined for edges. In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. More generally, the edge cut of G is a group of edges whose total removal renders the graph disconnected. The edge-connectivity λ(G) is the size of a smallest edge cut, and the local edge-connectivity λ(u,v) of two vertices u,v is the size of a smallest edge cut disconnecting u from v. Again, local edge-connectivity is symmetric. A graph is called k-edge-connected if its edge connectivity is k or greater.

類(lèi)似的，如果有一個(gè)邊集合，刪除這個(gè)邊集合以后，原圖變成多個(gè)連通塊，就稱這個(gè)點(diǎn)集為割邊集合。一個(gè)圖的邊連通度的定義為，最小割邊集合中的邊數(shù)。

[雙連通圖 割點(diǎn) 與橋]

Point Biconnected Component 無(wú)向圖點(diǎn)2連通分量與    cut point 割點(diǎn)

Edge Biconnected Component 無(wú)向圖邊2連通分量與    bridge 橋

如果一個(gè)無(wú)向連通圖的點(diǎn)連通度大于1，則稱該圖是點(diǎn)雙連通的(point biconnected)，簡(jiǎn)稱雙連通或重連通。一個(gè)圖有割點(diǎn)，當(dāng)且僅當(dāng)這個(gè)圖的點(diǎn)連通度為1，則割點(diǎn)集合的唯一元素被稱為割點(diǎn)(cut point)，又叫關(guān)節(jié)點(diǎn)(articulation point)。

如果一個(gè)無(wú)向連通圖的邊連通度大于1，則稱該圖是邊雙連通的(edge biconnected)，簡(jiǎn)稱雙連通或重連通。一個(gè)圖有橋，當(dāng)且僅當(dāng)這個(gè)圖的邊連通度為1，則割邊集合的唯一元素被稱為橋(bridge)，又叫關(guān)節(jié)邊(articulation edge)。

可以看出，點(diǎn)雙連通與邊雙連通都可以簡(jiǎn)稱為雙連通，它們之間是有著某種聯(lián)系的

[雙連通分支] 

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

[求割點(diǎn)與橋]

該算法是R.Tarjan發(fā)明的。對(duì)圖深度優(yōu)先搜索，定義DFS(u)為u在搜索樹(shù)（以下簡(jiǎn)稱為樹(shù)）中被遍歷到的次序號(hào)。定義Low(u)為u或u的子樹(shù)中能通過(guò)非父子邊追溯到的最早的節(jié)點(diǎn)，即DFS序號(hào)最小的節(jié)點(diǎn)。根據(jù)定義，則有：

Low(u)=Min
{
DFS(u)
DFS(v) (u,v)為后向邊(返祖邊) 等價(jià)于 DFS(v)<DFS(u)且v不為u的父親節(jié)點(diǎn)
Low(v) (u,v)為樹(shù)枝邊(父子邊)
}

一個(gè)頂點(diǎn)u是割點(diǎn)，當(dāng)且僅當(dāng)滿足(1)或(2)
(1) u為樹(shù)根，且u有多于一個(gè)子樹(shù)。
(2) u不為樹(shù)根，且滿足存在(u,v)為樹(shù)枝邊(或稱父子邊，即u為v在搜索樹(shù)中的父親)，使得DFS(u)<=Low(v)。

一條無(wú)向邊(u,v)是橋，當(dāng)且僅當(dāng)(u,v)為樹(shù)枝邊，且滿足DFS(u)<Low(v)。

[求雙連通分支]

下面要分開(kāi)討論點(diǎn)雙連通分支與邊雙連通分支的求法。

對(duì)于點(diǎn)雙連通分支，實(shí)際上在求割點(diǎn)的過(guò)程中就能順便把每個(gè)點(diǎn)雙連通分支求出。建立一個(gè)棧，存儲(chǔ)當(dāng)前雙連通分支，在搜索圖時(shí)，每找到一條樹(shù)枝邊或后向邊(非橫叉邊)，就把這條邊加入棧中。如果遇到某時(shí)滿足DFS(u)<=Low(v)，說(shuō)明u是一個(gè)割點(diǎn)，同時(shí)把邊從棧頂一個(gè)個(gè)取出，直到遇到了邊(u,v)，取出的這些邊與其關(guān)聯(lián)的點(diǎn)，組成一個(gè)點(diǎn)雙連通分支。割點(diǎn)可以屬于多個(gè)點(diǎn)雙連通分支，其余點(diǎn)和每條邊只屬于且屬于一個(gè)點(diǎn)雙連通分支。

對(duì)于邊雙連通分支，求法更為簡(jiǎn)單。只需在求出所有的橋以后，把橋邊刪除，原圖變成了多個(gè)連通塊，則每個(gè)連通塊就是一個(gè)邊雙連通分支。橋不屬于任何一個(gè)邊雙連通分支，其余的邊和每個(gè)頂點(diǎn)都屬于且只屬于一個(gè)邊雙連通分支。

[構(gòu)造雙連通圖]

有橋的連通圖必然有割點(diǎn)，有割點(diǎn)的連通圖不一定有橋(下圖可以很明顯得到)

如果一個(gè)圖有橋，則把此圖變成無(wú)橋的圖的最優(yōu)策略：

一個(gè)有橋的連通圖（其必然有割點(diǎn)），如何把它通過(guò)加邊變成邊雙連通圖？方法為首先求出所有的橋，然后刪除這些橋邊，剩下的每個(gè)連通塊都是一個(gè)邊雙連通子圖。把每個(gè)雙連通子圖收縮為一個(gè)頂點(diǎn)，再把橋邊加回來(lái)，最后的這個(gè)圖一定是一棵樹(shù)，邊連通度為1。

統(tǒng)計(jì)出樹(shù)中度為1的節(jié)點(diǎn)的個(gè)數(shù)，即為葉節(jié)點(diǎn)的個(gè)數(shù)，記為leaf。則至少在樹(shù)上添加(leaf+1)/2條邊，就能使樹(shù)達(dá)到邊二連通，所以至少添加的邊數(shù)就是(leaf+1)/2。具體方法為，首先把兩個(gè)最近公共祖先最遠(yuǎn)的兩個(gè)葉節(jié)點(diǎn)之間連接一條邊，這樣可以把這兩個(gè)點(diǎn)到祖先的路徑上所有點(diǎn)收縮到一起，因?yàn)橐粋€(gè)形成的環(huán)一定是雙連通的。然后再找兩個(gè)最近公共祖先最遠(yuǎn)的兩個(gè)葉節(jié)點(diǎn)，這樣一對(duì)一對(duì)找完，恰好是(leaf+1)/2次，把所有點(diǎn)收縮到了一起。

如果一個(gè)圖無(wú)橋有割點(diǎn)，則把此圖變成雙連通的最優(yōu)策略：

如果一個(gè)圖既有橋，又有割點(diǎn)，則把此圖變成雙連通的策略：（不是最優(yōu)。。。）

1 首先把圖變成無(wú)橋的

2 把有割點(diǎn)無(wú)橋的圖變成雙連通

（顯然這個(gè)算法不是最優(yōu)的。。關(guān)鍵問(wèn)題是把圖變成無(wú)橋的圖的時(shí)候的策略選擇！這個(gè)需要高手指點(diǎn)。。。）

A biconnected component (or 2-connected component) in graph theory is a maximalbiconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or articulation points. Specifically, a cut vertex is any vertex that when removed increases the number of connected components.

算法的基本描述：

The classic sequential algorithm for computing biconnected components in a connected undirected graph due to John Hopcroft andRobert Tarjan (1973) ^[1] runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd edition).

The idea is to run a depth-first search while maintaining the following information:

1. the depth of each vertex in the depth-first-search tree (once it gets visited), and
2. for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called thelowpoint.

The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of all neighbors of v (other than v's parent in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.

The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if v's lowpoint is at least as large as v's depth. This property can be tested once the lowpoint of v is computed (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of the descendants of v (by traversing the depth-first-search tree), and henceforth pretending that v had no children in the depth-first-search tree, so that the subgraph abovev will not descend into v's ancestors.

The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children. Thus, it suffices to simply build one component out of each child subtree of the root (including the root).

Each color corresponds to a biconnected component. Multi-colored vertices are cut vertices, and thus belong to multiple biconnected components.

引入割點(diǎn)的目的： 如果我們?nèi)サ魣D中的某個(gè)點(diǎn)之后，那么這個(gè)圖是否還是連通的！

引入2連通分量(塊)的目的：圖的某個(gè)子圖是否可以去掉一個(gè)點(diǎn)之后，仍然是連通的。也就是說(shuō)相對(duì)于這個(gè)子圖，沒(méi)有割點(diǎn)。此圖的割含有兩個(gè)點(diǎn)。

（注意一個(gè)圖的割和割點(diǎn)不是一個(gè)概念！）

Reference ：

http://www.byvoid.com/blog/biconnect/         byvoid的NX文章

Wiki 配圖

中科院研究生院算法分析設(shè)計(jì)講義（陳老師）