关于网络流

流网络：是一个有向图（可以有环），有两个特殊的点：一个是源点（出发点），一个是汇点，每条边都有属性，叫做容量（也就是每条边的权），

可以想象成一条河，每个点就是一个汇集处，边的容量就是一段的流量。

对于反向边，可以在中间加一个点，所以我们可以默认成不存在反向边

如果边不存在，那容量就是0；

可行流（f），从源点流出，如果满足2个条件就是可行流：1容量限制 2流量守恒（对于每个点，流进多少，就流出多少）

可行流流量值（|f|）=往外流的流量 – 流回来的流量（这里考虑了反向边，但基本上是不需要考虑的）

最大流：即最大的可行流

残留网络：针对流网络的某一条可行流而言，每个可行流都对应唯一的残留网络（Gf）

残留网络的点集就是原网络的点集，边集包括原网络的所有边，和所有反向边，

残留边的容量有两种情况

对于非反向边，也就是图里的边，就是他还没有用掉的容量值，啥意思？？不是说每条边都有一个最大流量吗，那残留网络的边值就是最大流量减去原流量。

对于反向边，就是这条边能退回去多少流量，那也就是这条边的原流量

那为啥要定义这个反向边呢？？对于任意一个点你可以选择走或者是不走，但是你走着走着就发现这条路不是最优解，那你就后悔了于是要返回，返回的流量就是原来流出的流量！！

原网络的可行流（f）和残留网络可行流（f’）有啥关系？

f+f’也是原网络的一个可行流。

证明：那就看是否满足容量限制和流量守恒

分类讨论：如果这两条边的方向是相同的，我们知道残留的最大值就是c（最大容量）-f，也就是说： 0<=f\'<=c-f，而原网络的的范围是 0<=f<=c，所以相加的范围就是:0<f+f\'<=c，那他们就不会超限制，所以满足容量限制

如果方向不同，那又退回来一些，所以肯定不会超过限制：即：c(u,v)>=f(u,v)+f\'(v,u)>=0

第二点就是流量守恒：

那我们可以看出来，反正两边总和是相同的，那就算是相减（反向）还是相加（正向），等号依旧是成立的

就好比 a=b , c=d => a+c=b+d , a-c=b-d

那这个可行流的流量怎么算？

| f + f\’ | = | f | + | f\’ |

得到性质：任何一个残留网络的大于零可行流都可以增加原网络里的可行流

换句话说，如果一个残留网络里没有了大于零的可行流，那原网络的可行流就一定是最大的

增广路径：

在残留网络里，从源点出发，沿着容量大于零的边，如果能走到终点的话，这条路径就是一条增广路径（一般不考虑环）

那由定义得，增广路径一定是一条可行流，有何用处？

割：

将点构成的集合V分成两部分：S和T，要求：S∪T=V，S∩T=∅，而且源点s∈S，汇点 t∈T。

那这个划分的结果就是一个割

1、割的容量：所有从S集合指向T集合的边的容量值和(顺序不能换），即c(S,T)=

最小割：割的最小容量

2.割的流量：从S指向T的流量-从T指向S的流量,即：

那就有以下性质：对于任意一个割，割的流量一定小于等于割的容量，即

证明：其实就是考虑不能超过最大流呗

还有，就是我们刚才不是得出了：可行流流量值（|f|）=往外流的流量 – 流回来的流量，那也就是：

那我们再进阶一下：

这个就很好理解了对吧，感性理解一下吧

那现在有个大问题：就是|f|与f（S,T）之间的关系：

来证明一下吧！

$\\because S\\cup T = V,S\\cap T = \\phi$

$\\thereforef(S,V)=f(S,S)+f(S,T)=0+f(S,T)$

$\\therefore f(S,T)=f(S,V)=f(s,V)+f(S-s,V)$

$\\because t\\notin S,s\\notin S-s$
$\\therefore t,s\\notin S-s$
$设S\’=S-s$
$\\therefore S\’是一个不包括汇点源点的集合，他一定满足流量守恒$
$\\therefore f(S\’,V)=\\sum_{u\\in S\’}^{}\\sum_{v\\in V}^{}f(u,v)- \\sum_{u\\in S\’}^{}\\sum_{v\\in V}^{}f(v,u)$
$=\\sum_{u\\in S\’}^{}(\\sum_{v\\in V}^{}f(u,v)-\\sum_{v\\in V}^{}f(v,u)$
$=\\sum_{u\\in S\’}^{}(0)$
$=0$
$\\therefore f(S,T)=f(s,T)$
$由定义得：f(s,V)=|f|$
$\\therefore f(S,T)=|f|$

其实要是是在理解不了（比如我），那就感性理解一下吧！

当然，还有另一种非常简单的解法(LaTeX在博客园上太太太丑了，所以还是换回来了那个字体）：

然后找到有相同的项的并合并，一约就发现有等于0的部分，然后就OK啦！！！但是由于本蒟蒻精力有限，剩下的证明就不再赘述，请谅解（其实是因为打这玩意真真真太麻烦了）

所以我们得出：

即：最大流<=最小割

下面开始进入核心部分：

关于最大流最小割定定理：

最大流=最小割

首先我们需要知道的是，对于某一个流网络来说：1可行流f是最大流 <=> 2可行流f的残留网络中不包括增广路 <=> 3存在某一个割，使得可行流的流量=割的容量

如何证明？

首先，如果 f 是最大流，而且残留网络中还有增广路，那么 f 肯定还能加，那 f 就不是最大流了，与前面假设矛盾，所以 1=>2，也就是说如果f是最大流，那f的残留网络一定不包括增广路。

其次，如果有一条可行流，他的流量等于割的容量，假设他不是最大流，那就会存在一条比他大的最大流，那这条最大流的流量一定大于割的容量，由于容量限制，这种情况是肯定不会发生的，所以如果存在一个割，他的容量等于一条可行流的流量，那么这条可行流一定是最大流，所以3=>1，搞定！

最后，将S集合定义为在残留网络中，从s（源点）出发，沿着容量大于0的可行流走，所有能走到的点，T=V – S，这就是一个合法的割，那么，设f(x,y)<c(x,y)，那么c(x,y)-f(x,y)，也就是残留网络中的容量f\'(x,y)就大于零，那也就说y这个点能从x这个点遍历到的，那么y就应该属于S，与原假设矛盾，所以f(x,y)=c(x,y)，那么对于任意的反向边一定等于0。此时我们得出，