基本概念
- 边 / 点割集：若边集 \(E'\) 使得割掉这些边之后 \(u\to v\) 不连通，则 \(E'\) 是 \((u,v)\) 的边割集。类似地定义点割集。
- 边 / 点连通度：若任意 \((u,v)\) 的割集大小都至少是 \(s\)，则 \(u,v\) 是 \(s-\)边连通的。类似地定义点连通度。
- Menger 定理：\(u\to v\) 的边连通度为 \(s\) 当且仅当存在至少 \(s\) 条边不交的从 \(u\to v\) 的路径，点连通度的情况类似。这实际上是最大流最小割定理的一个特化版本。
双联通性
-
点双连通分量的性质：
- 对于任意两点 \(u,v\)，存在同时包含 \(u,v\) 的简单环。由 Menger 定理立得。
- 对于点 \(u\) 和边 \(e\)，存在同时包含 \(u,e\) 的简单环；对于两条边 \(e_1,e_2\)，存在同时包含 \(e_1,e_2\) 的简单环。通过拆点可以转化到上面的情况。
- 共环：若存在简单环同时包含 \(e_1,e_2\)，则称它们是共环的。点双连通分量划分了共环关系导出的等价类。
-
一种刻画双连通分量的视角：耳分解。
- 定义 \((G_0,G_1,G_2,\cdots,G_k)\) 为 \(G\) 的耳分解，满足：\(G_k=G\)；\(G_0\) 为一个简单环；\(G_i\) 为 \(G_{i-1}\) 基础上添加一条简单路径或者简单环得到。若只添加简单路径，则称 \((G_0,G_1,G_2,\cdots,G_k)\) 为 \(G\) 的开耳分解。
- 一张图为边双连通图等价于它存在耳分解，一张图为点双连通图等价于它存在开耳分解。
- 类似可以定义强连通图的耳分解。可以证明，一张图能被定向为强连通图，当且仅当它为边双连通图。
割空间与环空间
- 割集：对于无向图 \(G=(V,E)\) 的二划分 \(V_1,V_2\)，其割集 \(E=\{e|(x,y),x\in V_1,y\in V_2\}\)，记作 \(C(V_1,V_2)\)。
- 图的割集与生成树割集的对应。
- 对于树，割集 \(E\) 对应的无序点集对 \((V_1,V_2)\) 唯一。
- 对于 \(G\) 的生成树 \(T\) 的割集 \(E'\)，存在唯一的 \(E'\subseteq E\) 为 \(G\) 的割集。原因是 \(E'\) 可以划分出点集。
- 割空间：若将割集看作 \(\mathbb{F}_2\) 上的 \(|E|\) 维向量，则一张图的所有割集构成 \(n-c\) 维线性空间。
- 只需证明割集和割集的对称差仍然是割集即可。该线性空间的一组基为一条树边和跨过它的非树边构成的割集的集合。
- 环空间：将图上的简单环看作 \(\mathbb{F}_2\) 上的 \(|E|\) 维向量，则一张图的所有简单环构成 \(m-n+c\) 维线性空间。
- 显然简单环与简单环的对称差仍然是简单环。该线性空间的一组基为一条非树边和它跨过的所有树边构成的环的集合。
- 判断割集的方法：假设有 \(t\) 条非树边，考虑 \(t\) 维向量：非树边只有它编号对应的那一维为 \(1\)，树边为跨过它的非树边的向量的和，则一个割集中所有边对应的所有向量的和为 \(0\)。
- 切边等价：对于两条边 \(e_1,e_2\)，若对于任意一个环，它或者同时包含 \(e_1,e_2\)，或者同时不包含 \(e_1,e_2\)，则称它们切边等价。
- 两条边切边等价当且仅当它们同时为割边，或者删去它们两条边之后，其所在的边双连通分量不连通。
- 判断割边等价的方式：\(e_1,e_2\) 切边等价当且仅当上文所述的向量相等。
- 非割边的切边等价类能被环空间整系数线性表出（ICPC 2015 World Final）。
有向图
-
动态可达性问题：bitset，询问分块。
-
在\(\bmod m\) 意义下的有向图任意路径边权集合。
- 对于强连通图上的一条边 \((u,v,w)\)，存在 \(v\to u\) 的路径使得它的边权和为 \(-w\)，这相当于建边 \((v,u,-w)\)，此时的有向图满足反对称性。
- 经过如上改造之后，有向图上的任意环的边权可以被所有仅包含一条非树边的边权整系数线性表出，与无向图的情况类似。
-
竞赛图的兰道定理：一张竞赛图的出度序列 \(d\) 从小到大排序后，满足 \(\sum_{i=1}^k d_i\geq \dbinom{k}{2}\)，其中满足 \(\sum_{i=1}^k d_i= \dbinom{k}{2}\) 的为缩点后的分界点。