@
前言
初一的证明简直就是SB，错漏百出。。。
术语介绍
前向弧：(E)中的边。
可行流：上文介绍的是最大流，可行流即为满足(f,c)约束的一个流，最大流是没有增广路径的可行流，对于一个流(f)，(|f|)就是其流量。
割
割是啥子东西？
割是针对只有前向弧的有向图的，需要注意的。
一个割就是把点集(V)分成(S,T)集，我们记为((S,T))，其中(st∈S,ed∈T)。
而一个割的容量是(sumlimits_{u∈S,v∈T,(u,v)∈E}c(u,v))，流量是(sumlimits_{u∈S,v∈T,(u,v)∈E}f(u,v)-sumlimits_{v∈S,u∈T,(u,v)∈E}f(u,v))
定理1： 一个割的流量绝对≤割的容量。
定理2：对于任意一个可行流(f)，割的流量等于(|f|)。
证明：
这个时候，割等于(S)到(T)的所有出边和(T)到(S)的所有入边。
推导：
对于一个点(u∈V-left { st,ed
ight })，满足下面这条
(sumlimits_{u∈V}f(u,v)-sumlimits_{u∈V}f(v,u)=0)。
我们把(|f|)表示出来：
(|f|=sumlimits_{v∈V}f(st,v)+sumlimits_{u∈S-left { st
ight }}sumlimits_{v∈V}f(u,v)-sumlimits_{u∈V}sumlimits_{v∈S-left { st
ight }}f(u,v)=sumlimits_{u∈S}sumlimits_{v∈V}f(u,v)-sumlimits_{u∈V}sumlimits_{v∈S}f(u,v))
(V=S∪T,S∩T=0)
所以
(|f|=sumlimits_{u∈S}sumlimits_{v∈T}f(u,v)+sumlimits_{u∈S}sumlimits_{v∈S}f(u,v)-sumlimits_{u∈T}sumlimits_{v∈S}f(u,v)-sumlimits_{u∈S}sumlimits_{v∈S}f(u,v)=sumlimits_{u∈S}sumlimits_{v∈T}f(u,v)-sumlimits_{u∈T}sumlimits_{v∈S}f(u,v))。
证毕。
定理三：(|f|=f(S,T)≤c(S,T))
因此，最大流≤最小割的容量。
最大流最小割定理证明
终于到这个地方了。。。
设(f)为流网络(G=(V,E))中的一个流，那么下面的条件是等价的：
- (f)是(G)的一个最大流。
- 残余网络(G_{f})不包括任何增广路径。
- (|f|=c(S,T))，(c(S,T))是某个切割，很明显这个切割是最小割。
((1)->(2))，存在增广路怎么可能是最大流。
((2)->(3))，假设(G_{f})中不存在增广路径，那么我们定义(u)能走到(v)，仅当((u,v)∈E,f(u,v)<c(u,v))或者((v,u)∈E,f(v,u)>0)，很明显，(st)到(ed)的每条路径都不是增广路，所以路径上一定有((u,v)∈E,f(u,v)=c(u,v))或者((v,u)∈E,f(v,u)=0)，这个时候定义(st)能走到的点集为(S)，(ed)能走到的点集为(T)即可。
此时(u∈T,v∈S,f(u,v)=0)（不是的话，一定可以到(v)），所以(|f|=sumlimits_{u∈S}sumlimits_{v∈V}f(u,v)=sumlimits_{u∈S}sumlimits_{v∈V}c(u,v)=c(S,T))。
满足条件。
((3)->(1))，因为(|f|≤c(S,T))，所以当(|f|=c(S,T))时，(|f|)最大，所以(f)为最大流。
((2)->(3)->(1))证毕。
所以，最小割就是最大流，不存在增广路就是最大流。
参考资料
论如何卡掉Dinic(我没看懂)
咕咕讨论，Zadeh Construction是个什么东西
算法导论爷Orz