求割点、割边、强连通分量总结

tarjan求图的联通性问题是一种高效的模板化方法。其依赖于$dfn$与$low$求解，十分巧妙。
kosaraju依赖更加巧妙的性质，证明略为复杂。

本文递交已结束。

tarjan求解

对于一棵树树，其各节点时间戳如下图：

研究树的联通性问题是没有意义的，除了时间戳（$dfn$）外，另外引入一个追溯值（$low$）记录对于一个节点$u$其本身及其深度优先搜索子树所有点可以回到的最小的时间戳，对于一个普通的有向图其深度优先搜索时间戳[]及追溯值() 为：

割点判定法则：在无向图中，当某一点$u$，其任意一个出边所连的点$v$ 当且仅当满足$dfn[u]<=low[v]$（该点有一个子树中所有的点都没有办法追溯回$u$ 的祖先，则当将$u$ 删除时该子树会断开）时$u$ 为该图的割点，特别的若$u$ 为根节点，只要有超过两个子节点即为割点。

割边判定法则：在无向图中，与求解割点类似的在深度优先搜索生成树中某一条边$(u,v)$，当且仅当$dfn[u]<low[v]$时，该边为割边。

强连通分量的求解方法：在有向图的深度优先搜索生成树中若存在某一点$u$当满足$dfn[u]=low[u]$时，$u$ 与其子树中所有的点都在同一个强连通分量中。利用栈记录下搜索顺序，当找到一个节点$u$ 时从栈顶到栈中的$u$之间的所有元素即为其子树，它们在同一个强连通分量中。

Kosaraju求强连通分量

谭老师在课堂上详细地证明了Kosaraju的正确性，证明思路较为复杂。Kosaraju与Tarjan思路相类似，首先在图中任选一个节点的作为起点开始dfs，按照退出的顺序给节点编号就是搜索森林的后序序列。再每次选择未访问的标号最大的点进行搜索，其搜索树的节点都在同一个强连通分量中。

证明是比较复杂的。首先对于第一次搜索，编号小的到编号大的一定存在一条直接路径，除非它们不在同一棵树中。将图求逆后，编号小的一定不能再通过原来的路径到达编号大的，那么从编号大的节点开始dfs一遍，能够到达的节点在原图一定至少存在两条路径是让它们互相相连的。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章