跳转到内容

双连通图

维基百科,自由的百科全书


图论中,一个点双连通图是一个连通且“不可分离”的,意思是如果任何一个顶点被去除,图仍是连通的。所以这样一个双连通图就没有割点英语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

参见

参考