最小割树
最小割树适用于无向图，通过构造 Gomory-Hu 树或等价流树，你可以快速求出图中任意两点间的最小割的值，甚至可以求出这个割的划分方案。
一些定义
- 原图的点集 \(\mathbf V\)，边集 \(\mathbf E\) 沿用上文的定义。
- 割表示划分出来的两个点集，割的值表示横跨切割的边的权值之和（与上文的割的容量定义类似
无向图里面说容量感觉怪怪的）。 - 上文使用 \((\mathbf S, \mathbf T)\) 来描述一个割，而这一章中只会使用一个点集（通常是 \(\mathbf W\)）描述一个割，因为划分出来另一部分的点集一定是 \(\mathbf V \setminus \mathbf W\)。
- 定义 \(c(\mathbf U) = w(\mathbf U, \mathbf V \setminus \mathbf U)\)（简化割的值的表示）。
- 定义 \(c(u, v)\) 为图中 \(u\) 和 \(v\) 之间的最小割（下面的费用流也有同样的函数，不过这两者的定义不同，请注意这点）。
- 我们对上文的 \(w(\mathbf S, \mathbf T)\) 的定义做一些改变，上文中要求 \((\mathbf S, \mathbf T)\) 是一个割，但本章中我们不要求这一点（值得注意的是，由于这是无向图，所以 \(w(\mathbf S, \mathbf T) = w(\mathbf T, \mathbf S)\)）。
前置知识
三角形不等式
并不是几何的那个三角形不等式
三角形不等式
对于任意三点 \(a, b, c\)，有 \(c(a, b) \geq \min\{c(a, c), c(b, c)\}\)。
证明
对于任意三点 \(a, b, c\)，因为 \(a, b, c\) 等价，不妨假设 \(c(a, b) \leq c(a, c), c(b, c)\)。接下来考虑 \(c\) 在最小割中的哪一侧，因为 \(a, b\) 的等价，所以不妨假设 \(c\) 在最小割中 \(b\) 那一侧，这样，\(a\) 和 \(b\) 的割同时也是 \(a\) 和 \(c\) 的割，因此有 \(c(a, b) \geq c(a, c)\)。因为假设 \(c(a, b) \leq c(a, c)\)，所以 \(c(a, b) = c(a, c)\)。因此，对于任意三点 \(a, b, c\)，\(c(a, b), c(a, c), c(b, c)\) 中，一定有两个相等的较小值，一个较大值。因此命题得证。
推论
推论
对于任意两点 \(u, v\)，有 \(c(u, v) \geq \min\{c(u, w_1), c(w_1, w_2), \cdots, c(w_{k - 1}, w_k), c(w_k, v)\}\)。
证明
根据三角形不等式，有 \(c(u, v) \geq \min\{c(u, w_1), c(w_1, v)\}\)，然后反复将 \(c(w_i, v) \geq \min\{c(w_i, w_{i+1}), c(w_{i+1}, v)\}\) 代入即可得到结论。
子模函数、对称函数与反模函数
子模函数
对于全集 \(\mathbf V\)，\(\mathbf U \subset \mathbf V\)，\(f(\mathbf U)\) 是一个关于集合的函数。若对于任意 \(\mathbf A, \mathbf B \subset \mathbf V\)，有 \(f(\mathbf A) + f(\mathbf B) \geq f(\mathbf A \cap \mathbf B) + f(\mathbf A \cup \mathbf B)\)，则称 \(f\) 是一个子模函数。
结论
割的值函数 \(c\) 是子模函数。
证明
对于点集 \(\mathbf A, \mathbf B\)，我们设 \(\mathbf C = \mathbf A \cap \mathbf B, \mathbf D = \mathbf V \setminus (\mathbf A \cup \mathbf B), \mathbf E = \mathbf A \setminus \mathbf B, \mathbf F = \mathbf B \setminus \mathbf A\)，于是，\(\mathbf A = \mathbf C \cup \mathbf E, \mathbf B = \mathbf C \cup \mathbf F, \mathbf A \cap \mathbf B = \mathbf C, \mathbf A \cup \mathbf B = \mathbf C \cup \mathbf E \cup \mathbf F\)。
因此，割的值函数是子模函数。
对称函数
对于全集 \(\mathbf V\)，\(\mathbf U \subset \mathbf V\)，\(f(\mathbf U)\) 是一个关于集合的函数。若对于任意 \(\mathbf U \subset \mathbf V\)，有 \(f(\mathbf U) = f(\mathbf V \setminus \mathbf U)\)，则称 \(f\) 是一个对称函数。
显然割的值函数是一个对称函数。
反模函数
对于全集 \(\mathbf V\)，\(\mathbf U \subset \mathbf V\)，\(f(\mathbf U)\) 是一个关于集合的函数。若对于任意 \(\mathbf A, \mathbf B \subset \mathbf V\)，有 \(f(\mathbf A) + f(\mathbf B) \geq f(\mathbf A \setminus \mathbf B) + f(\mathbf B \setminus \mathbf A)\)，则称 \(f\) 是一个反模函数。
结论
若 \(f\) 同时是子模函数和对称函数，那么 \(f\) 也是反模函数。
证明
因此，割的值函数也是反模函数。
核心引理
核心引理
对于两点 \(s, t\) 间的最小割 \((\mathbf W, \mathbf V \setminus \mathbf W)\)，则对于任意 \(u, v \in \mathbf W\)，存在 \(u, v\) 的最小割 \(\mathbf X, \mathbf V \setminus \mathbf X\)，使得 \(\mathbf X \subset \mathbf W\)。
证明
不失一般性地，我们令 \(s \in \mathbf W, s \in \mathbf X, u \in \mathbf X\)。然后进行分类讨论：
- 若 \(t \notin \mathbf X\)，因为 \(c\) 是子模函数，所以有 \(c(\mathbf W) + c(\mathbf X) \geq c(\mathbf W \cap \mathbf X) + c(\mathbf W \cup \mathbf X)\)。注意到 \(\mathbf W \cap \mathbf X\) 也是 \(u, v\) 的割，\(\mathbf W \cup \mathbf X\) 也是 \(s, t\) 的一个割，因此有 \(c(\mathbf W \cap \mathbf X) \geq c(\mathbf X), c(\mathbf W \cup \mathbf X) \geq c(\mathbf W)\)，因此所有不等号都应该取等。也就是说，\(\mathbf W \cap \mathbf X\) 也是 \(u, v\) 的最小割。
- 若 \(t \in \mathbf X\)，因为 \(c\) 是反模函数，所以有 \(c(\mathbf W) + c(\mathbf X) \geq c(\mathbf W \setminus \mathbf X) + c(\mathbf X \setminus \mathbf W)\)。注意到 \(\mathbf W \setminus \mathbf X\) 也是 \(u, v\) 的一个割，\(\mathbf X \setminus \mathbf W\) 也是 \(s, t\) 的一个割，因此有 \(c(\mathbf W \setminus \mathbf X) \geq c(\mathbf X), c(\mathbf X \setminus \mathbf W) \geq c(\mathbf W)\)，因此所有不等号都应该取等。也就是说，\(\mathbf W \setminus \mathbf X\) 也是 \(u, v\) 的最小割。
核心引理揭示了最小割可以不交叉，它是最小割树实现的基础。
Gomory-Hu 树
定义一棵树 \(T = (\mathbf V, \mathbf E_T)\)，若断开 \((s, t) \in \mathbf E_T\)，若形成的其中一个连通块的点集为 \(\mathbf W\)，则 \((\mathbf W, \mathbf V \setminus \mathbf W)\) 是 \(s, t\) 的一个最小割，且这条边的边权为最小割的值。这样的树称为 Gomory-Hu 树。\(val(u, v)\) 表示树上 \(u, v\) 两点之间的边权（\((u, v) \in \mathbf E_T\)）
结论
对于所有 \(u, v \in \mathbf V\)，令 \((s, t)\) 为树上 \(u, v\) 的路径上权值最小的边，那么 \(s, t\) 的最小割就是 \(u, v\) 的最小割。
证明
由三角形不等式，\(c(u, v) \geq c(s, t)\)，又因为 \(s, t\) 的最小割也是 \(u, v\) 的割，因此 \(c(u, v) \leq c(s, t)\)。因此 \(c(u, v) = c(s, t)\)。
递归建树
令图 \(G = (\mathbf V, \mathbf E)\)，点集 \(\mathbf R \subset \mathbf V\)。定义 \(\mathbf R\) 在 \(G\) 中的 Gomory-Hu 树为一个二元组 \(T, \mathbf C\)，其中 \(T = (\mathbf R, \mathbf E_T)\)，\(\mathbf C = (\mathbf C_r | r \in \mathbf R)\)，是一个对 \(\mathbf V\) 的划分。这个划分有三个性质：
- 对于 \(u \in \mathbf V\)，存在唯一的 \(r\) 使 \(u \in \mathbf C_r\)。
- 对于 \(r \in \mathbf R\)，\(r \in \mathbf C_r\)。
- 对于所有的边 \((s, t) \in \mathbf E_T\)，设删掉 \((s, t)\) 后形成的其中一个连通块为 \(\mathbf X\)，则 \(s, t\) 在 原图 \(G\) 中的最小割是 \(\bigcup_{r \in \mathbf X} \mathbf C_r\)。
看起来很抽象
如何理解这个集合的划分？
每个 \(\mathbf C_r\) 都是一个集合。点集 \(\mathbf R\) 为这次递归处理的点集，而这次递归会处理出来一个 \(\mathbf C\)，你可以将 \(\mathbf C\) 理解为所有 \(\mathbf C_r\) 构成的集合，所有在 \(\mathbf R\) 内的点都是一个其中一个集合的代表点。每个点只能在其中一个集合中出现。这次递归同样会处理出来一个点集为 \(\mathbf R\) 的 Gomory-Hu 树 \(T\)，对于 \(T\) 中的每一条边 \((s, t)\)，其在原图中的最小割一定可以用若干个 \(\mathbf C_r\) 的并集表示出来。
伪代码
Tip
\((\mathbf C_r^1 | r \in \mathbf R_1), (\mathbf C_r^2 | r \in \mathbf R_2)\) 中的上标表示的是编号。
对于当前处理的点集 \(\mathbf R\) 和上一层递归传进来的图 \(G\)，首先任选两点 \(r_1, r_2\)，求出一个 \(r_1, r_2\) 在图 \(G\) 中的最小割（注意不是原图）。然后进行缩点，并以缩点之后的 \(G_1, G_2\) 为基础求两个 Gomory-Hu 树。最后进行划分的合并（具体合并方法的解释在下文）。
越来越抽象了
正确性证明
证明
我们先说明建树过程中集合划分的前两条性质是怎么保证的。对于 \(|\mathbf R| = 1\) 的情况，这两条性质显然成立。接着使用归纳法，假设当前得到的 \((\mathbf C_r^1 | r \in \mathbf R_1)\) 和 \((\mathbf C_r^2 | r \in \mathbf R_2)\) 都满足这两条性质，在处理 \((\mathbf C_r | r \in \mathbf R)\) 时，我们先将以 \(\mathbf R_1\) 和 \(\mathbf R_2\) 中的点为代表点的集合平凡地赋值给 \((\mathbf C_r | r \in \mathbf R)\)，这样，每个元素在划分中都被包含了两次。接着，我们找到了 \(r' \in \mathbf R_1, r'' \in \mathbf R_2\)，使 \(v_1, v_2\) 中包含的点分别属于 \(\mathbf C_{r'}^1, \mathbf C_{r''}^2\)。因为 \(G_1\) 是把一些点缩成 \(v_1\) 之后的图，因此一定存在且仅存在一个 \(r'\) 满足 \(v_1 \in \mathbf C_{r'}^1\)。同理，一定也存在 \(r''\) 使 \(v_2 \in \mathbf C_{r''}^2\)。同时，因为 \(v_1, v_2\) 包含的点恰好覆盖了 \(\mathbf V\) 中的所有点，因此 \(\mathbf C_{r'}, \mathbf C_{r''}\) 去掉 \(v_1, v_2\) 中包含的点之后就满足了这两条性质。
划分的第三个性质看起来非常像最小割树的性质，因此我们一起证明。对于 \(|\mathbf R| = 1\) 的情况，这两条性质显然成立。接着使用归纳法，假设当前得到的 \((T_1, (\mathbf C_r^1 | r \in \mathbf R_1))\) 和 \((T_2, (\mathbf C_r^2 | r \in \mathbf R_2))\) 都满足这两条性质。由核心引理，\(\mathbf R_1, \mathbf R_2\) 内部的点都满足 Gomory-Hu 树的定义。同时 \(r_1, r_2\) 的割也是 \(r', r''\) 的割，也就是说，我们仅需要证明 \(c(r', r'') \geq c(r_1, r_2)\) 即可。接下来，分三种情况：
- \(r' = r_1, r'' = r_2\)，显然成立。
- \(r' = r_1, r'' \ne r_2\) 或 \(r' \ne r_1, r'' = r_2\)，我们讨论 \(r' \ne r_1, r'' = r_2\) 的情况，另一种情况同理。因为 \(G_1\) 中，\(\mathbf V \setminus \mathbf W\) 被缩成一个点 \(v_1\)，同时 \(r_2 \in \mathbf V \setminus \mathbf W, v_1 \in \mathbf C_{r'}^1\)，因为 \(\mathbf C^1\) 满足划分的第三条性质，因此 \(r', r_1\) 的割同时也是 \(r_1, r_2\) 的割，因此有 \(c(r', r_1) \geq c(r_1, r_2)\)。根据三角形不等式，有 \(c(r', r'') \geq \min\{c(r', r_1), c(r_1, r_2)\}\)，所以 \(c(r', r'') \geq c(r_1, r_2)\)。因此成立。
- \(r' \ne r_1, r'' \ne r_2\)，这种情况的证明与上一种类似。我们通过同样的方法求出 \(c(r', r_1) \geq c(r_1, r_2), c(r'', r_2) \geq c(r_1, r_2)\)。根据三角形不等式，有 \(c(r', r'') \geq \min\{c(r', r_1), c(r_1, r_2), c(r_2, r'')\}\)，所以 \(c(r', r'') \geq c(r_1, r_2)\)。因此成立。
关于划分的第三条性质，因为 \(T\) 此时已经是 Gomory-Hu 树，所以 \(\mathbf R\) 中任意两点 \(u, v\) 的最小割就是两者路径上边权最小的边 \((s, t)\)，然后进行分类讨论：
- 若 \(s, t\) 就是 \(r', r''\)，最小割就是 \(\mathbf W, \mathbf V \setminus \mathbf W\)，可以用划分表示。
- 若 \(s, t\) 都在 \(\mathbf R_1\) 或 \(\mathbf R_2\) 中，因为 \(\mathbf C^1, \mathbf C^2\) 都是满足第三条性质的，因此也可以用划分表示。
因此最小割树的正确性得证。
非递归建树
在递归建树时我们需要记录划分 \(\mathbf C\)，而这看起来就不好实现。考虑到集合划分的顺序是无关紧要的，于是我们可以使用非递归建树。
伪代码
我们将一个集合内编号最小的点记为这个集合的代表点。我们对每一个结点记一个 \(fa_i\)，若 \(i\) 是所在集合的代表点，那么 \(fa_i\) 代表一条树边，表示 \(i\) 所在集合和 \(fa_i\) 所在集合之间有一条边（建树结束之后所有集合都将只有一个元素，也就变成点与点之间的边）；若 \(i\) 不是所在集合的代表点，那么 \(fa_i\) 指向这个集合的代表点。
我们定义 \(w_i\) 为 \(i\) 向 \(fa_i\) 连边的权值。
还有比这更抽象的吗
开始时所有结点在同一个集合里，代表点是 \(1\)。然后从 \(u = 2\) 开始枚举点，将 \(u\) 从所在集合中划分出去，并成为新集合的代表点。记 \(v = fa_u\)，具体方法是：将当前集合外的所有集合缩点之后求 \(u, v\) 之间的最小割，同时因为编号在 \(u\) 之前的点已经分离出去；且由于 \(u\) 是编号最小的非代表点，所以 \(u\) 一定会成为新集合的代表点。
我们设 \(u\) 所在的集合为 \(\mathbf R\)，\(u, v\) 的最小割为 \((\mathbf W, \mathbf V \setminus \mathbf W)\)，且 \(u \in \mathbf W\)。对于 \(\mathbf V \setminus {u}\) 的所有点 \(x\)，如果 \(x \in \mathbf W, fa_x = v\)，分两种情况讨论：
- 如果编号比 \(u\) 小，也就是说这是一条 \((x, v)\) 的树边，我们将 \(fa_x \gets u\)，也就是将 \(x\) 代表的集合连到 \(u\) 代表的集合上。
- 如果编号比 \(u\) 大，我们将 \(fa_x \gets u\)，也就是将 \(x\) 划分进 \(u\) 代表的集合中。
因此，无论哪种情况，我们都只需要将 \(fa_x \gets u\)。
接下来，我们需要处理 \(fa_v\)。如果 \(fa_v \in \mathbf W\)，因为我们需要让在最小割同一侧的几个集合相邻（参考递归实现），所以我们需要将 \(u\) 和 \(v\) 交换位置；否则平凡地连边即可。
正确性证明
证明
因为 \(fa_i\) 的定义，集合的划分显然符合前两条性质。由于集合划分的方式和递归实现的相同，因此也符合第三条性质。关于连边，我们可以将递归实现看成一步到位地按照割的划分得到了连边的两个点（因为递归实现是先处理出来划分后的点集的 Gomory-Hu 树，因此可以直接找出连边的两个点，但非递归实现是逐渐划分的集合，所以边的端点也需要在不断划分中确定），因此非递归实现也可以建出 Gomory-Hu 树。
等价流树
有时我们并不需要求出最小割的具体方案，而是只需要求出最小割的值，因此我们可以使用建树更加容易的等价流树。等价流树要求若 \((u, v) \in \mathbf E_T\)，\(val(u, v) = c(u, v)\)。它的性质为任意两点间的最小割等于这两点在树上的路径上的权值最小值。
Tip
函数定义同 Gomory-Hu 树。
递归建树
伪代码
正确性证明
证明
我们发现，根据核心引理，若求出来的 \(\mathbf W \not \subset \mathbf R\)，有 \(\mathbf R \cap \mathbf W\) 或 \(\mathbf R \setminus \mathbf W\) 是 \(s, t\) 的最小割。但是无论是哪一种都不影响要递归处理的点集，因此我们不需要进行缩点。
若 \((s, t) \in \mathbf E_T\)，虽然断开 \(s, t\) 之间的边形成的两个连通块不一定是 \(s, t\) 之间的最小割。但因为核心引理，若 \(s, t\) 的最小割为 \((\mathbf W, \mathbf V \setminus \mathbf W)\)，那么 \(\mathbf R \cap \mathbf W\) 或 \(\mathbf R \setminus \mathbf W\) 是 \(s, t\) 的最小割。因此 \(s, t\) 间的最小割是能将递归处理的两个集合中的点割开的。
对于 \(|\mathbf R| = 1\) 的情况，等价流树的性质显然成立。接着使用归纳法，假设当前得到的 \(T_1\) 和 \(T_2\) 都满足性质。令 \(\mathbf R_1 = \mathbf R \cap \mathbf W, \mathbf R_2 = \mathbf R \setminus \mathbf W\)，对于任意两点 \(u, v \in \mathbf R\)，进行分类讨论：
- 若 \(u, v \in \mathbf R_1\) 或 \(u, v \in \mathbf R_2\)，\(u, v\) 之间的路径也在 \(T_1\) 或 \(T_2\) 中，因此成立。
- 因为 \(u, v\) 等价，因此不妨假设 \(u \in \mathbf R_1, v \in \mathbf R_2\)。此时 \(s, t\) 的割同时也是 \(u, v\) 的一个割，因此有 \(c(u, v) \leq c(s, t)\)。对于 \(u, s\) 路径上的边权最小的边 \((r_1, r_2)\) 所对应的最小割，\(t\) 要么在 \(s\) 侧，要么在 \(u\) 侧。
- 如果 \(t\) 在 \(s\) 的一侧，由核心引理，\(v\) 也在 \(s\) 侧，因此 \(r_1, r_2\) 的割也是 \(u, v\) 的割，\(c(u, v) \leq c(r_1, r_2)\)。
-
如果 \(t\) 在 \(u\) 的一侧，\(r_1, r_2\) 的割也是 \(s, t\) 的割，\(c(s, t) \leq c(r_1, r_2)\)。
对于 \(t, v\)，同理。因为三角形不等式，\(c(u, v) \geq \min\{(u, s)\text{ 路径上最小的边权}, c(s, t), (t, v)\text{ 路径上最小的边权}\}\)。结合上面的结论，有 \(c(u, v)\) 等于 \(u, v\) 路径上最小的边权。
非递归建树
伪代码
\(fa_i\) 与 Gomory-Hu 树的非递归实现有同样的用处，不过若 \(u\) 是集合的代表点，\((u, fa_u)\) 的含义不再是集合之间的连边，而是 \(u\) 和 \(fa_u\) 两点之间的连边。因为等价流树只需要划分集合并连边，因此实现简单了许多。对于当前处理的点 \(u\)，它是集合的代表点，集合中所有的其他点的编号一定比 \(u\) 大，且不需要改变已有的树边，因此从 \(u + 1\) 开始找即可。
一些结论
结论
- 要构造 Gomory-Hu 树或等价流树，需要做 \(|\mathbf V| - 1\) 次最小割。
- 无向图最小割最多有 \(|\mathbf V| - 1\) 种取值。