最大流最小割定理-三亩地-编程学习日记

设流网络为有向图 \(G = (V, E)\)，其中：

容量函数 \(c : E \to \mathbb{R}^+\)，边 \((u,v)\) 的容量记为 \(c(u,v) \ge 0\)。
源点 \(s \in V\)，汇点 \(t \in V\)，且 \(s \neq t\)。
一个流 \(f : E \to \mathbb{R}\) 满足：
- 容量限制：对每条边 \((u,v) \in E\)，有 \(0 \le f(u,v) \le c(u,v)\)。
- 流量守恒：对每个顶点 \(u \in V \setminus \{s, t\}\)，有 \(\sum_{v \in V} f(u,v) = \sum_{v \in V} f(v,u)\)。

流 \(f\) 的值定义为从源点流出的净流量：

\[|f| = \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s). \]

一个割 \((S, T)\) 是将顶点集划分为两个子集，使得 \(s \in S\)，\(t \in T\)，\(T = V \setminus S\)。割的容量定义为从 \(S\) 到 \(T\) 的所有边的容量之和（只计方向从 \(S\) 指向 \(T\) 的边）：

\[c(S,T) = \sum_{u \in S} \sum_{v \in T} c(u,v). \]

定义流过割的净流量（考虑两个方向的边）：

\[f(S,T) = \sum_{u \in S} \sum_{v \in T} f(u,v) - \sum_{u \in S} \sum_{v \in T} f(v,u). \]

对任意流 \(f\) 与任意割 \((S,T)\)，有

\[|f| = f(S,T) \le c(S,T). \]

证明：
由流量守恒，对所有 \(u \in S \setminus \{s\}\)，它流入与流出 \(S\) 内部的净效果为零。通过将所有属于 \(S\) 的顶点的流量守恒方程相加，可得

\[|f| = \sum_{u \in S}\left(\sum_{v \in V} f(u,v) - \sum_{v \in V} f(v,u)\right) = f(S, V) - f(V, S). \]

由于 \(S \cup T = V\) 且 \(S \cap T = \emptyset\)，将 \(V\) 拆为 \(S\) 和 \(T\)，化简后即得 \(|f| = f(S,T)\)。
又由容量限制 \(f(u,v) \le c(u,v)\) 且反向边流量非负，有

\[f(S,T) \le \sum_{u \in S}\sum_{v \in T} c(u,v) - 0 = c(S,T). \]

因此 \(|f| \le c(S,T)\)。
由此立即可得：最大流的值 ≤ 最小割的容量。

设 \(f\) 是网络中的一个最大流（即不再存在增广路径）。定义残量网络 \(G_f = (V, E_f)\)，其中对原网络每条边 \((u,v)\)：

在 \(G_f\) 中，令

\[S = \{ v \in V \mid \text{存在从 } s \text{ 到 } v \text{ 的路径} \}, \quad T = V \setminus S. \]

显然 \(s \in S\)。因 \(f\) 是最大流，残量网络中 不存在从 \(s\) 到 \(t\) 的路径（否则沿该路径增广可增大流值），故 \(t \in T\)。因此 \((S,T)\) 是一个合法割。

考察原网络中所有跨越割的边：

对任意 \(u \in S, v \in T\)，若原网络中存在边 \((u,v)\)，则必有 \(f(u,v) = c(u,v)\)。
否则 \(c(u,v) - f(u,v) > 0\)，在 \(G_f\) 中会有正向边 \((u,v)\)，由于 \(u\) 从 \(s\) 可达，\(v\) 也会变得从 \(s\) 可达，与 \(v \in T\) 矛盾。
对任意 \(u \in S, v \in T\)，若原网络中存在边 \((v,u)\)（方向从 \(T\) 到 \(S\)），则必有 \(f(v,u) = 0\)。
否则 \(f(v,u) > 0\)，在 \(G_f\) 中会有反向边 \((u,v)\)，同样导致 \(v\) 从 \(s\) 可达，矛盾。

因此，

\[f(S,T) = \sum_{u \in S}\sum_{v \in T} f(u,v) - \sum_{u \in S}\sum_{v \in T} f(v,u) = \sum_{u \in S}\sum_{v \in T} c(u,v) - 0 = c(S,T). \]

由引理有 \(|f| = f(S,T)\)，于是

\[|f| = c(S,T). \]

即该流 \(f\) 的值等于割 \((S,T)\) 的容量。

结合第 2 节（任意流值 ≤ 任意割容量）与第 4 节（存在一个流与一个割使值相等），可得：

日记详情