是 ix35 老师论文的学习笔记，同时也用作连通性相关知识梳理。
可能不会包含很多定义，只会挑重要的写。会包含一些例题。
定义与记号
\(u \rightsquigarrow v\) 代表 \(u\) 到 \(v\) 的一条路径。有时也会用这个记号表示连通性。
无向图
-
点/边连通度：若 \(u, v\) 任意点割集大小不小于 \(s\)，则称 \(u, v\) 是 s-点连通的，同理定义 t-边连通。\(u, v\) 的点/边连通度是上述 \(s, t\) 的最小值。图 \(G\) 的点/边连通度为所有点对间点/边连通度的最小值。
-
Menger 定理：对于任意 \(u \neq v\)，其是 k-边连通的，当且仅当存在 \(k\) 条 \(u \rightsquigarrow v\) 的边不交路径。点连通同理。
Menger 定理可以用最大流最小割定理证明。注意在定理中并没有要求路径不同，例如一张 \(2\) 个点的完全图对于任意 \(k\) 都有 k-点连通。
双连通性
即上述定义中的 2-连通性。
边双连通
边双连通性是点集 \(V\) 上的一种等价关系，也就是说，你可以根据边双连通性对 \(V\) 进行划分（实际上就是能把图划分成若干边双连通块），因此边双连通性会比点双连通性容易考虑。
注意到在 tarjan 算法的过程中满足 \(dfn_u = low_u\) 的点 \(u\) 是一个边双连通块的最浅点，并且其 dfs 树子树内还未被删除的点就构成一个边双连通分量，因此可以在 \(O(n + m)\) 的时间内求出所有边双连通分量。
注意将边双缩点后图会形成一棵树。可以利用此性质解决边双相关问题。
点双连通
点双连通并不不是 \(V\) 上的等价关系，因此考虑起来没有边双那么容易。
可以使用 tarjan 算法求出图的所有点双连通分量。
点双连通的一些性质：
-
对于 \(u \neq v\)，存在经过 \(u, v\) 的简单环。
这是 Menger 定理的直接推论。因为存在两条除端点外不相交的路径。 -
对于任意一点 \(u\) 和任意一边 \(e\)，存在经过 \(u, e\) 的简单环。对于 \(e_1 \neq e_2\)，存在经过 \(e_1, e_2\) 的简单环。
将边 \(x \rightarrow y\) 拆成 \(x \rightarrow z \rightarrow y\)，然后用上条性质证明即可。 -
对于 \(u \neq v\) 和 \(e\)，存在经过 \(e\) 的简单路径 \(x \rightsquigarrow y\)。
根据上条性质，选择一个包含 \(u, e\) 的环 \(C\)，尝试找到一条 \(y \rightsquigarrow x\) 的路径 \(P\)，满足 \(P, C\) 的交集大于 \(1\)。注意 \(x\) 显然在交集中，若找不到这样的 \(P\)，说明 \(y\) 无法通过非 \(x\) 的点走到 \(C\) 上的点，那么 \(x\) 是割点，矛盾。设 \(P, C\) 交集中最靠近 \(y\) 的点为 \(u\)，那么选择 \(x \rightsquigarrow u\) 并包含 \(e\) 的路径和 \(u \rightsquigarrow y\) 拼起来就行。 -
共环：对于 \(e_1, e_2\)，若存在一个简单环同时包含 \(e_1, e_2\)，则称它们是共环的。注意到其实共环是一种对于边的等价关系，点双连通性实际上相当于一种对边集的划分。