最大流最小割定理

其本质说白了就是一句话——水流的最大流量取决于最细的水管的容量

如果一条弧的两个顶点分别属于顶点集S和T(一个顶点在S,另一个在T),
那么这条弧称为割CUT(S,T)的一条割边。

从S指向T的割边是正向割边;

从T指向S的割边是逆向割边。

割CUT(S,T)中所有正向割边的容量和称为割CUT(S,T)的容量。
不同割的容量不同。

定理一:
如果f是网络中的一个流,CUT(S,T)是任意一个割,
那么f的值等于正向割边的流量与负向割边的流量之差。

推论1:
如果f是网络中的一个流,CUT(S,T)是一个割,那么f的值不超过
割CUT(S,T)的容量。


推论2:
网络中的最大流不超过任何割的容量


定量2:
在任何网络中,如果f是一个流,CUT(S,T)是一个割,
且f的值等于割CUT(S,T)的容量,那么f是一个最大流,
CUT(S,T)是一个最小割(容量最小的割)。


定量3:最大流最小割定量:
在任何的网络中,最大流的值等于最小割的容量。


结论1:
最大流时,最小割cut(S,T)中,正向割边的流量=容量,
逆向割边的流量为0。否则还可以增广。

原文地址:https://www.cnblogs.com/scau20110726/p/2791523.html