双连通分量及圆方树学习笔记

无向图的双连通分量

  由标题可知,本文只研究无向图中的双连通分量。在无向图中,图中双连通分量分为两种,分别是点-双连通分量,简称点双;边-双连通分量,简称边双。

  对于一个连通图,如果任意两点之间至少存在两条经过不同点的路径,则这个图是一个点-双连通。同理,如果任意两点之间至少存在两条经过不同边的路径,则这个图是一个边-双连通。在无向图中,我们将点-双连通的极大子图称为点-双连通分量,将边-双连通的极大子图称为边-双连通分量。

点-双连通分量求法

割顶

边-双连通分量求法

圆方树

圆方树的求法

广义圆方树

总结

挖坑待填。

本博客所有文章均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处
本文链接:https://23forever.com/2019/07/05/biconnected-component/