【图论】双连通分量

前言

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

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

概念

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

割边与割点

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

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

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

什么是双连通分量

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

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

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

求双连通分量

先观察