雙連通圖

在圖論中，一個點雙連通圖是一個連通且「不可分離」的圖，意思是如果任何一個頂點被去除，圖仍是連通的。所以這樣一個雙連通圖就沒有割點（英語：Biconnected component）。2-點連通（英語：k-vertex-connected graph）的性質和點雙連通是幾乎等價的，除了一條邊連接兩個點構成的圖，它是點雙連通的，但不是2-點連通的。

這個性質在維護一個有2度冗餘的圖中特別有用，為了防止去除一條邊（或連接）之後的不連通。

由於冗餘的這種特性，雙連通圖的使用在網絡領域非常重要（參見網絡流）。

定義

一個雙連通的無向圖是一個連通圖，不會因為刪除任一個節點（和它的附帶邊）而變得不連通。

一個雙連通的有向圖中，對於任何兩個頂點v和w，都有兩條從v到w的有向路徑，且除了v和w以外沒有其他公共頂點。

n個節點的不可分離 (或 2-連通) 圖 (或塊)的可能情況數 （OEIS數列A002218）

頂點	可能性數量
1	0
2	1
3	1
4	3
5	10
6	56
7	468
8	7123
9	194066
10	9743542
11	900969091
12	153620333545
13	48432939150704
14	28361824488394169
15	30995890806033380784
16	63501635429109597504951
17	244852079292073376010411280
18	1783160594069429925952824734641
19	24603887051350945867492816663958981

• 
  一個4個頂點和4條邊的雙連通圖。
• 
  一個不是雙連通的圖。去除頂點x會使圖不連通。
• 
  一個5個頂點和6條邊的雙連通圖。
• 
  一個不是雙連通的圖。去除頂點x會使圖不連通。

參見

• 雙連通分量（英語：Biconnected component）

參考

• Eric W. Weisstein. "Biconnected Graph." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/BiconnectedGraph.html （頁面存檔備份，存於網際網路檔案館）
• Paul E. Black, "biconnected graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html （頁面存檔備份，存於網際網路檔案館）

• Java實現雙連通分量構成的樹 （頁面存檔備份，存於網際網路檔案館），使用JBPT庫（見BCTree類）。