2重連結グラフ

ウィキペディア

2重連結グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/11/09 13:18 UTC 版)

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

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

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

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

定義

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

2重連結有向グラフは、任意の二つの頂点 v および w に対して、v と w 以外に共通の頂点を含まないような 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

例

• [1]

関連項目

• 2重連結成分

参考文献

• 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: http://www.nist.gov/dads/HTML/biconnectedGraph.html

外部リンク

• The tree of the biconnected components Java implementation in the jBPT library (see BCTree class).