Algorithms: 网络流：最大流、最小割

Flow Network

网络流图 $G=(V,E,c)$ 是一张有向图，其中每一条有向边 $e=(u,v)$ 有容量 (capacity) $c(u,v)\ge 0$ . 除此之外， $G$ 中还有两个特殊节点 source $s$ 和 sink $t$ .

在此基础上，我们定义流 (Flow). $G$ 上的流 $f$ 给每一条边 $e=(u,v)$ 都赋上一个实数 $f(u,v)$ 且满足：

每一条边的流量都不会超过其容量 capacity.
$f(u,v)\le c(u,v)$
除了源点与汇点，其余每一点都满足：流入的流量和流出的流量相等。
$\forall v\in V-\{s,t\}, \sum_{(x,v)\in E} f(x,v)=\sum_{(v,y)\in E} f(v,y)$

什么是割？

图的一个“割” (Cut) 是指将图分成两个点集 $A,B$ 且源点 $s\in A$ ，汇点 $t\in B$ . 定义 Capacity of Cut $cap(A,B)=\sum_{e\text{ out of }A}c(e)$

Flow Value Lemma

令 $f$ 为 $G$ 上任意的流， $(A,B)$ 为 $G$ 上任意的割（ $s\in A,t\in B$ ），则必有

\text{value}(f)=\sum_{e \text{ out of }A}f(e)-\sum_{e\text{ into }A} f(e)

证明

考虑 $A$ 中的每一个节点，除了源点 $s$ 以外，其余所有点都满足 $\text{outflow}(v)=\text{inflow}(v)$ ，而 $s$ 的 $\text{inflow}(s)=0$ ，所以

\mathrm{value}(f)=\sum \mathrm{outflow}(s)=\sum_{v\in A} \mathrm{outflow}(v)-\mathrm{inflow}(v)

我们再来考察 $\sum_{v\in A}\mathrm{outflow}(v)$ ，检查所有边，可得

\sum_{v\in A}\mathrm{outflow}(v)=\sum_{e\text{ inside }A}f(e)+\sum_{e\text{ out of }A}f(e)

同理对 inflow 有

\sum_{v\in A}\mathrm{inflow}(v)=\sum_{e\text{ inside }A}f(e)+\sum_{e\text{ into }A}f(e)

两式相减可得

\mathrm{value}(f)=\sum_{e\text{ out of }A}f(e)-\sum_{e\text{ into }A}f(e)

由此也可以推得几个推论

Corollary 1

\mathrm{value}(f)\le \mathrm{cap}(A,B)

证明

\begin{aligned} \mathrm{value}(f)&=\sum_{e\text{ out of }A} f(e)-\sum_{e\text{ into }A} f(e)\\ &\le \sum_{e\text{ out of }A} f(e)\\ &\le\sum_{e\text{ out of }A} \mathrm{cap}(e)\\ &=\mathrm{cap}(A,B) \end{aligned}

Theorem 3

令 $f$ 为图上的流且使得 $G_f$ 不存在增广路，那么存在一种 cut $(A,B)$ 使得 $\mathrm{value}(f)=cap(A,B)$ .

证明

既然 $G_f$ 上已经不存在增广路，那么 $G_f$ 天然的可以被划分为两个集合 $A,B$ ，其中 $A=\set{v:s\to v},B=V-A$

这也就是说，原图 $G$ 中， $A$ 到 $B$ 的有向边的 residual capacity 均为 $0$ ，根据 Flow Value Lemma， $\mathrm{cut}(A,B)$ 就是一种符合条件的割。

最大流最小割定理

\text{Max Flow}=\text{Min Cut}