无向图的桥与割点

Content #

如果在去掉无向连通图G中的一条边e后，图G分裂为两个不相连的子图，那么e为图G的桥或割边。

如果在去掉无向连通图G中的一个点v及与v关联的所有边后，图G分裂为两个或两个以上不相连的子图，那么v为图G的割点。

注意：

1. 删除边时，只把该边删除即可，不要删除与边关联的点；
2. 删除点时，要删除该点及其关联的所有边。

割点与桥的关系：

1. 有割点不一定有桥，有桥一定有割点；
2. 桥一定是割点依附的边。

From #

《算法训练营入门篇》 陈小玉

Links #