数学グラフ理論における2重連結グラフ(2じゅうれんけつグラフ、: biconnected graph)とは、任意の頂点が取り除かれても連結であるという意味で「分離不可能」なグラフのことを言う。したがって、2重連結グラフには関節点英語版は存在しない。

2-連結であるという性質は、2重連結性と基本的に同値である。ただし、二つの頂点からなる完全グラフはしばしば、2重連結であるが2-連結ではないと見なされることに注意されたい。

この性質は特に、一つの(あるいは、接続)を取り除く際の非連結を防ぐための、グラフの2重冗長性を維持する上で有用である。

この冗長性に関する性質により、2重連結グラフは、ネットワークの分野(フローネットワークを参照されたい)において非常に重要となる。

定義

編集

2重連結無向グラフは、どの一つの頂点(およびそれに接続する辺)を取り除いても非連結とならない連結グラフである。

2重連結有向グラフは、任意の二つの頂点 v および w に対して、vw 以外に共通の頂点を含まないような v から w への二つの有向路が存在するグラフである。

n 個の頂点を持つ分離不可能(あるいは2-連結)グラフ(あるいはブロック)(オンライン整数列大辞典の数列 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

関連項目

編集

参考文献

編集

外部リンク

編集