最大流与最小割

网络流

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

对于每个边，我们定义了3个属性：

1. capacity: 用C表示，最大容量，上图中边的数值就是capacity
2. flow: 用F表示，每条边的流量
3. residual: 用R表示，残留，R = C - F

斜对称性：F = -F. 基于斜对称性，当flow为负时，残留值可能大于最大容量

对于上图，假如存在一条流的路径：S->A->C->T. 那么这条路径的流就是这条路径的所有边的最大残留的最小值，也就是R=12. 此时，可以更新每条边的flow和residual, F=0+12=12, R=16-12=4, F=0+12=12, R=12-12=0, F=0+12=12, R=20-12=8, 每次边的flow增加一定数量，residual就必定减少一定数量，这个数量可以为负值. 这条路径被称为增广路，原因是路上的每个边的残留值都大于0，意味着可以有流从这个路径上通过。

最大流

一般使用Edmonds-Karp算法，即最短路径增广算法，简称EK算法。

通过多次运行BFS算法，得到一条增广路，也就是从S到T的可行的流大于0的路径，然后更新相关边的属性值，其中有一点要注意：设这条路径的流是flow，则flow+=flow, flow+=(-flow), residual-=(-flow)，每次一个边的残留值减去一个值，对应的反向边的残留值就会加上一个值。不断运行BFS算法，直到找不到一条增广路了。

下面是一个运行EK算法的例子：黑色数字表示残留值，一开始残留值就是最大容量值，红色数字表示流量值。

1. 第一次运行BFS得到一个增广路：

   

   

   更新残留值：

   

   

2. 第二次运行BFS算法得到一个增广路

   

   

   更新残留值：

   

   

3. 第三次运行BFS得到一个增广路

   

   

   更新残留值：

   

   

最小割

最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割

我们把S能到达的点集设为s, 不能到达的点集设为t，构造一个割集C[s,t]。如下图所示

C[s,t] 中含有边, , , .
其中满流边是前三个，它们构成了最小割。

赏

谢谢你请我吃糖果