无向图的双连通

点连通度与边连通度
在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。一个图的点连通度的定义为,最小割点集合中的顶点数。 
类似的,如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合。一个图的边连通度的定义为,最小割边集合中的边数。 [双连通图、割点与桥]  
如果一个无向连通图的点连通度大于1,则称该图是点双连通的(point biconnected),简称双连通或重连通。一个图有割点,当且仅当这个图的点连通度为1,则割点集合的唯一元素被称为割点(cut point),又叫关节点(articulation point)。  
如果一个无向连通图的边连通度大于1,则称该图是边双连通的(edge biconnected),简称双连通或重连通。一个图有桥,当且仅当这个图的边连通度为1,则割边集合的唯一元素被称为桥(bridge),又叫关节边(articulation edge)。   
可以看出,点双连通与边双连通都可以简称为双连通,它们之间是有着某种联系的

图G的所有子图G‘中,如果G’是双连通的,则称G‘为双连通子图,如果一个双连通G’不是任何一个双连通子图的真子图,则G‘为图G的极大双连通子图。双连通分量或重连通分量就是图的极大双连通分量,特别的,点双连通分量又称为块。

总而言之,如果一个图存在关节点,或者关节边,那么它就不是双连通图,因为如果存在关节点或者关节边,那么它里面就出现了一个点或者一条边必须经过,(我个人的理解),也就不是双连通了

点双连通分量:

就是找图G的一个子图,这个子图没有关节点,也就是这个子图的最小割点集合大于一,边双连通分量可以类似理解

怎么求点双连通分量:

思路和求强连通分量的Tarjan算法类似。

如果对原图进行深度优先搜索,根据点双连通分量的定义,任何一个点双连通分量都是原图的一颗深度优先搜索子树

原文地址:https://www.cnblogs.com/GODLIKEING/p/3429307.html