网络流中的一些概念
- 边（弧）：在网络流问题中基本上所有的边都为有向边，所以在不加说明的情况下，文中出现的所有边都为有向边，有向边也成为弧，记为有序对$(a,b)$
- 图：一堆点加上一堆边就是一张图，也就是说，图是边集加上点集，用$G=\langle V,E\rangle$
- 路径：图中的一条路径就是一串相连的点，一条路径$v_1,v_2,\cdots\cdots,v_n$满足$\forall i\in [1,n],v_i\in V$且$\forall i\in [1,n),(v_i,v_{i+1})\in E$或$(v_{i+1},v_i)\in E$
- 前向弧：一条路径$v_1,v_2,\cdots\cdots,v_n$中，如果$(v_i,v_{i+1})\in E$，则称$(v_i,v_{i+1})$为前向弧
- 后向弧：一条路径$v_1,v_2,\cdots\cdots,v_n$中，如果$(v_{i+1},v_i)\in E$，则称$(v_i,v_{i+1})$为后向弧
- 割：一个图中如果存在一个边集$E’$，使得删除$E’$中的边后，原图分为两个集合，且这两个集合没有任何连边，那么$E’$就称为图$G$的一个割
- 边的容量：一条边所能承受的流量上界称为容量，$(u,v)$的容量用$C(u,v)$表示，类似于水管的截面面积，水管的截面面积就是它所能承受的水流流量上界
- 割的容量：把图$G$分为两个集合$S$和$T$的割中的所有边的流量之和记为$C(S,T)$，即$C(S,T)=\sum\limits_{u\in S,v\in T,(u,v)\in E} C(u,v)$
- 流量：类似于容量，用$F(u,v)$表示一条边的流量，$F(S,T)$表示一个割的流量
- 增广路： 一条路径，满足前向弧的流量严格小于容量，后向弧的流量大于$0$
- 可行流：从源点出发，到汇点结束，所有边的流量未超过容量且除源点和汇点外，流入任意一点的流量等于流出这一点的流量（如果你学过高中物理中的电学，你可以把这个理解为基尔霍夫第一定律）
- 最大流：可行流中流量最大的流
- 最小割：把源点和汇点分成两个集合，容量最小的割
- 残余网络：对于任意的流$f$，建立新图$G_f$满足连边方式相同，边的容量等于原边的容量减去流量（当然，如果新的边的容量为$0$，去掉这条边也无所谓）
性质&定理证明
性质1
可行流的流量等于它的一个割的流量
证明：假设割将源点（$V_S$）和汇点（$V_T$）分为两个集合$S$和$T$，可行流流量为$F$
$\therefore$当$T=\{V_T\}$时，$F(S,T)=\sum\limits_{(x,V_T)\in E} F(x,V_T)=F$
$\therefore$假设当$T\subsetneq T’$时成立
$\therefore$当$T=T’$时，设$V_P\in T$
$\therefore~F(S,T)=F(S\cup\{V_P\},T\setminus {V_P})-\sum\limits_{(V_P,x)\in E,x\in T} F(V_P,x)+\sum\limits_{(V_P,x)\in E,x\in S} F(V_P,x)=F(S\cup\{V_P\},T\setminus {V_P})=F$推论1
可行流的流量小于等于它的一个割的容量
证明：由性质1知，可行流的流量等于它的一个割的流量，小于等于这个割的容量性质2
若残余网络中仍有增广路，那么可行流$F$不是最大流
证明：$\because$增广路的前向弧可以增加流量，后向弧可以减少流量
$\therefore F$可以继续增大
$\therefore$可行流$F$不是最大流性质3
若残余网络中无增广路，则存在一个割，使得割的容量等于可行流的流量
证明：$\because$残余网络中无增广路
$\therefore$原图中的每一条从源点到汇点的路径，都一定有一个前向弧的流量为容量或有一个后向弧的流量为$0$
$\therefore$设集合$S$为从源点出发，不经过流量为容量的前向弧和流量为$0$的后向弧所能到达的所有点的集合，$T=V\setminus S$
$\therefore$$F=F(S,T)=\sum\limits_{u\in S,v\in T,(u,v)\in E} F(u,v)=$前向弧总流量-后向弧总流量$=$前向弧总容量$-0=$前向弧总容量$=C(S,T)$性质4
对于一个可行流，若存在一个它的割，使得割的容量等于可行流的流量，则这个可行流为最大流，且这个割为最小割
证明：设可行流的流量为$F$，割的容量为$C$
假设$C$不是最小割的容量
$\therefore$存在一个割的流量为$C_0$，且$C_0<C$
又$\because F\leqslant C_0$
$\therefore C\leqslant C_0$，矛盾！
$\therefore$这个割为最小割
$\therefore F$到达了流量的上界
$\therefore$这个可行流的最大流
特别注意，这个性质并不代表最大流等于最小割（虽然这是对的），因为我们并没有说明这样的割一定存在
最大流最小割定理
最大流（的流量）等于最小割（的容量）
证明：取图$G$的最大流$F$
$\therefore$根据性质2的逆否命题可知：残余网络中无增广路
$\therefore$根据性质3可知：存在一个割，使得割的容量等于最大流的流量
$\therefore$根据性质4可知：这个割为最小割
$\therefore$最大流等于最小割
这样，我们就完成了网络流中最重要！最重要！最重要！ 的定理：最大流最小割定理，请大家一定记住这个定理，因为有时在解题过程中，我们需要使用最小割的方式来思考问题，最终通过最大流的算法解决
如果你难以理解我写的证明，那么你只要把这个定理的表述背下来即可（惊奇的发现表述和名称一样长耶！）