先把重要的事实贴在这里
搜索树
有向图:树边,返祖边,前向边,横叉边
无向图:树边,返祖边(另一种角度看就是前向边,其实区别不大;但一定没有横插边)
v-Dcc
顶点数不超过2一定是vDcc。否则
- 无割点
- 任意两条边,存在简单环
- 任意两点有点不同不重复路径,即在简单环中
无割点,vBCC间有公共点,则公共点为原图的割点。而割点至少属于两个vBCC,非割点只属于一个vBCC
点双连通分量构成对所有边集的一个划分。
两个点双连通分量最多只有一个公共点,且必为割点。进一步地,所有点双与割点可抽象为一棵树结构。
桥
必定在搜索树上
e-Dcc等价定义
无桥
任意边在简单环中
任意两点存在任意边不重复的路径
边双连通分量构成对所有点集的一个划分。
两个边双连通分量最多只有一条边,且必为桥。进一步地,所有边双与桥可抽象为一棵树结构。
点双联通不具有传递性,边双联通具有
非联通求连通分量
分量内等价 缩点
特殊情况