强连通分量中的一个点属于且仅属于一个边双连通分量。
缩点时,同一连通分量的点缩成一个点,最终会变成一个 DAG。唯一需要注意的是,重新建图时要判断原边的两个点是否在同一个强连通分量内。
点双连通分量删掉任意一个点后仍连通,任意两个点双连通分量至多有一个共同点(因此不会有共同边,否则必然属于同一个分量),且该共同点为割点。一个点可以属于多个点双连通分量。
缩点时,同一连通分量的点缩成一个点,同时保留割点,根据从属关系将分量与割点依次相连。如果把同一连通分量的点都连到对应的割点上,貌似就是一棵圆方树(或森林)了。
特殊地,$K_1,K_2$ 是点双连通分量。
边双连通分量删掉任意一条边后仍连通,任意两个边双连通分量互不相交(因此不会有共同点,否则必然属于同一个分量),且两个边双连通分量之间以割边链接。一个点最多属于一个边双连通分量(可以不属于任何边双连通分量)。
缩点时,同一连通分量的点缩成一个点,整个图会变成一个树(或森林)。
特殊地,$K_1$ 是边双连通分量。
割点和割边没有必然关系:两个端点是割点的边不一定是割边,割边的两个端点也不一定是割点。
下图的 $2, 4$ 是割点,但 $(2, 4)$ 不是割边:
下图的 $(1, 2)$ 是割边,但 $1, 2$ 不是割点: