网络流-最小割

定义

给定一个网络 \(G\)，在边集中选择一些边删除使得源点 \(S\) 与汇点 \(T\) 不连通。定义删除边 \(x\to y\) 的代价为 \(C_{x\to y}\)，则最小割即即使对于所有的割，删除的边代价最小和。

最大流最小割定理

内容

对于一个网络流图 \(G\)，其中有源点 \(s\) 和汇点 \(t\)，那么下面三个条件是等价的：

1. 流 \(f\) 是图 \(G\) 的最大流
2. 残量网络 \(G_f\) 不存在增广路
3. 对于 \(G\) 的某一个割 \((S,T)\) ，此时流 \(f\) 的流量等于其容量

证明

増广路算法基础，\(1\Rightarrow 2\) 正确性显然。割的容量是流量的上界，\(3\Rightarrow 1\) 正确性显然。

然后证明 \(2\Rightarrow 3\)。

假设残留网络 \(G_f\) 不存在增广路，所以在残留网络 \(G_f\) 中不存在路径从 \(s\) 到达 \(t\) 。

我们定义 \(S\) 集合为：当前残留网络中 \(s\) 能够到达的点。同时定义 \(T=V-S\)。此时 \((S,T)\) 构成一个割 \((S,T)\) 。且对于任意的 \(u\in S,v\in T\)，边 \((u,v)\) 必定满流。若边 \((u,v)\) 不满流，则残量网络中必定存在边 \((u,v)\)，所以 \(s\) 可以到达 \(v\)，与 \(v\) 属于 \(T\) 矛盾。

因此有 \(f(S,T)=\sum f(u,v)=\sum c(u,v)=C(S,T)\)。