【图论】双连通分量

【图论】双连通分量


前言#

在学习双连通分量之前请先了解强连通分量,有助于理解双连通分量,其中相同的概念不再赘述。

我的强连通分量笔记在:【图论】强连通分量

概念#

强连通分量是对于有向图而言的,而双连通分量是对于无向图而言的。

割边与割点#

在无向图中, 割点:去掉一个点及与其相邻的所有边,无向图中的连通分量增加,则称该点为割点。 割边:去掉一条边,无向图中的连通分量增加,则称该边为割边。 割点与割边的关系:

  1. 有割点不一定有割边,有割边一定有割点。
  2. 割边的两个端点中一定有一个是割点。

详细内容请阅读:【图论】割边与割点

什么是双连通分量#

根据上面割边与割点的定义,我们可以把双连通分量分成边双点双两种。

  1. 边双:对于一个图,假如仅仅对于该图而言其中没有割边,那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边,每一个点之间仍然是连通的。
  2. 点双:对于一个图,假如仅仅对于该图而言其中没有割点,那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边,每一个点之间仍然是连通的。

需要注意的是点双与强连通分量和边双不同,它会与其他点双相交,需要注意

求双连通分量#

先观察#