1. 基本概念
流网络
(G = (V,E))
有向图，一个源点，一个汇点。每条边都有一个属性（容量）。
不考虑反向边
可行流
可行流 (f) 需要满足
- 容量限制 （ (0 le f(u,v) le c(u,v)) )
- 流量守恒 （除了源点和汇点，其余点的流入等于流出）
(|f|) 表示可行流的流量
最大流
指的是 最大可行流
残留网络
针对流网络的某一条流
记作 (G_f) ，是由流 (f) 决定的
(V_f = V) , (E_f = E + E) 的反向边
残留网络 + 残留网络的一个可行流 = 原流网络的一个可行流
增广路径
在残留网络中从源点出发边权都大于0，到汇点结束的简单路径叫做增广路径。
- 增广路径一定是一个可行流
- 增广路径流量大于0
若对于一个可行流 (f) ,其 残留网络 (G_f) 若不存在增广路，则可以断定 (f) 是一个最大流
割
流网络 (G = (V,E))
把点集 (V) 分成 (S), (T) , (S cap T = empty) , (S cup T = V)
(s in S) , (t in T)
割的容量
所有从 (S) 到 (T) 的边的容量之和 (c(S,T) = sum_{uin S} sum_{v in T} c(u,v))
最小割指割的容量的最小值
割的流量
(f(S,T) = sum_{uin S}sum_{vin T}f(u,v) - sum_{vin T}sum_{uin S}f(v,u))
对任意的割，任意的一个可行流，割的流量一定小于等于割的容量
$forall S,T forall f , f(S,T) le c(S,T) $
对任意的割，任意的可行流，一定有割的流量等于可行流的流量
(forall S,T forall f \|f| = f(S,T))
证明
首先有
(f(S,T) = -f(T,S)) , (f(X,X)=0)
(f(S,X cup Y) = f(S,X) + f(S,Y)) , (X cap Y = empty)
(f(X cup Y, T) = f(X,T) + f(Y,T) , X cap Y = empty)
[f(S,T) = f(S,V) - f(S,S)\=f(S,V)\=f(s,V) + f(S-s,V)\=f(s,V) =|f| ]
最大流最小割定理
- 流 (f) 是最大流
- 流 (f) 的残留网络中不存在增广路
- 存在某个割 ([S,T]) , (|f| = c(S,T))
三者相互等价
一推二和三推一都比较简单
- ①推②
反证，若存在增广路，则可以更大流量
- ③推①
最大流 (ge |f|)
最大流 (le c(S,T) = |f|)
所以 (|f|) = 最大流
最小割 (le c(S,T) = |f| le) 最大流
此时还有 最小割=最大流
- ②推③
(S) , 在 (G_f) 中，从 (s) 出发沿容量大于0的边走，所有能走到的点
(T = V - S) ,因为没有增广路，所以 (S,T) 是一个割
(xin S,y in T) , 有 (f(x,y) = c(x,y)) ,反向边 (f(y,x) = 0)
所以 (|f| = c(S,T))