雙連通圖

移除少於兩點依然連通之圖


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

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

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

定義

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

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

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

參見

參考