网络流_1 网络流基本概念
网络流__1 网络流基础
流网络
如图为一个流网络,边权为最大流量c，记作
其中V为点集，E为边集。
可以想象成从源点源源不断的将水流向汇点的过程
其中，不考虑反向边，假如有反向边，可以通过加点来转化成没有反向边的情况
流量 定义：从源点往外净流出的量
可行流
即每一条边设计一个流量，记作
流量守恒即对于某个点流入的流量等于流出的流量
如图便是一个可行流,满足对于任意一点都有流出=流入：
对于一个可行流，每秒从源点流向汇点的流量的值/速率记作：
即往外流的流量流回去的流量：
最大流：
即所有可行流中流量值最大的可行流
残留网络
对于流网络的某一条可行流来说，残留网络与其一一对应，记作;
假定流网络G=(V,E),f为图G中的一个流，定义其残存网络的残存容量：
简单来说，对于原流网络的一个流来说，其残留网络的残存容量有两种形式，一种是同向的，流网络容量-当前流量；另一种是反向的，数值等于当前流的大小
定义如下表示残留网络中一个合法流f'对于原网络中的流f的递增
较为直观：f'(v,u)=f(u,v)
引理1
设G=(V,E)为一个流网络，源点为s，汇点为t，设f为G中的一个流。设Gf是由流f所有道德G的残留网络，设f’为Gf中的一个流，那么有：
证明：
f+f'也为G的一个可行流,即从容量限制和流量守恒来证明
推论：
- 可行流的残留网络内求得的任何一个值大于0的可行流都可以增加原网络的可行流
- 若原网络对应的残留网络的可行流的流量大于0，则原网络必定不是最大流，反之可证明是最大流
增广路径
对于给定流网络G=(V,E)和流f，增广路径p是其残存网络Gf中一条从源结点s到汇点t的简单路径，其中每一条边的容量都大于0.
对于对于G(V,E)的某一可行流 f 的残留网络上的某一可行流对应一条增广路径 f’，有f+f'仍然是G中的一个可行流，因此得到定理：
增广路径的残存容量：
我们称增广路径p上能够为每条边增加的流量的最小值为残存容量，即：
此处定义的残存容量与残留网络中的残存容量稍微不同，即最小值
割
对于一个流网络G=(V,E),可将其点集V分成两个不重不漏的集合S，T，有
其中有以下限制：
割的容量 c(S,T)
所有从S指向T的有向的容量之和
割的流量
所有从S到T的的流量与从T到S的流量之差：
性质1:
设f为流网络G的一个流，该流网络的源节点为s,汇点为t,设(S,T)为流网络G的任意切割，则横跨切割(S,T)的净流量：
即对于每一个割的流量，都能对应一个流网络中的流量
证明：
由引理1
等价于：
性质2：
换句话来说，对于流网络任意流，都小于任意割的容积，因此就有最大流小于等于最小割。其中注意，最大流指流网络的最大流量，最小割指的是最小割的容量
最大流最小割定理
以下三个定理相互等价
f是G中的一个最大流- 残留网络
Gf不包括任何增广路径 |f|=c(S,T),其中(S,T)是流网络G的某个切割
证明：
证明思路为证明1能推出2，2能推出3，3能推出1
1=>2：
2=>3
使用构造法：构造一个点集S，将起点s放入S，从Gf中从s出发沿容量大于0的边走，将所有能走到的点加入S，由于不包含增广路径，所以必然有t不属于S
因为加入f(x,y)<c(x,y)则x可以走到y，因此y应该在S中矛盾。a,b同理
3=>1