2重連結グラフ
表示
数学のグラフ理論における2重連結グラフ(2じゅうれんけつグラフ、英: biconnected graph)とは、任意の頂点が取り除かれても連結であるという意味で「分離不可能」なグラフのことを言う。したがって、2重連結グラフには関節点は存在しない。
2-連結であるという性質は、2重連結性と基本的に同値である。ただし、二つの頂点からなる完全グラフはしばしば、2重連結であるが2-連結ではないと見なされることに注意されたい。
この性質は特に、一つの辺(あるいは、接続)を取り除く際の非連結を防ぐための、グラフの2重冗長性を維持する上で有用である。
この冗長性に関する性質により、2重連結グラフは、ネットワークの分野(フローネットワークを参照されたい)において非常に重要となる。
定義
[編集]2重連結無向グラフは、どの一つの頂点(およびそれに接続する辺)を取り除いても非連結とならない連結グラフである。
2重連結有向グラフは、任意の二つの頂点 v および w に対して、v と w 以外に共通の頂点を含まないような v から w への二つの有向路が存在するグラフである。
頂点 | 可能性の数 |
---|---|
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 |
例
[編集]関連項目
[編集]参考文献
[編集]- 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).