维基百科
双连通图
在图论中，一个点双连通图是一个连通且“不可分离”的图，意思是如果任何一个顶点被去除，图仍是连通的。所以这样一个双连通图就没有割点。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 |
-
一个4个顶点和4条边的双连通图。
-
一个不是双连通的图。去除顶点x会使图不连通。
-
一个5个顶点和6条边的双连通图。
-
一个不是双连通的图。去除顶点x会使图不连通。
参见 编辑
- 双连通分量
参考 编辑
- 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类）。