网络流-最小割

约定不等于承诺〃 2022-05-28 08:43 224阅读 0赞

最大流最小割定理：最大流最小割定理是[网络流][Link 1]理论的重要定理。是指在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。即在任何网络中，最大流的值等于最小割的容量。

最大流

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

最小割

割是网络中定点的一个划分，它把网络中的所有顶点划分成两个顶点集合S和T，其中源点s∈S,汇点t∈T。记为CUT(S,T)，满足条件的从S到T的最小割（Min cut）。

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

证明：  
　　设X和Y是网络中的两个顶点集合，用f（X,Y）表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X中，弧头在Y中：

![500fd9f9d72a60591828dc462334349b033bbab5.jpg][]

）的流量和。只需证明：f=f(S,T)-f(T,S) 即可。

下列结论成立：

如果X∩Y=

![03087bf40ad162d9e0bc5f401adfa9ec8a13cd1f.jpg][]

，那么：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2) ，f((X1∪X2),Y)=f(X1,Y)+f(X2,Y) 成立。  
　　根据网络流的特点：

如果V既不是源点也不是汇点，那么： f(\{V\},S∪T)-f(S∪T,\{V\})=0；任何一个点，流入的与流出的量相等。

如果V是源，那么：f(\{V\},S∪T)-f(S∪T,\{V\})=f。

对于S中的所有点V都有上述关系式，相加得到：f(S,S∪T)-f(S∪T,S)=f 。

又因为： f(S,S∪T)-f (S∪T,S)= (f(S,S)+f (S,T))-(f(S,S) +f (T,S))= f(S,T)- f(T,S)，

所以：f= f(S,T)- f(T,S) 定理得证  \[2\]    。

推论一：  
　　如果f是网络中的一个流，CUT(S,T)是一个割，那么f的值不超过割CUT(S,T)的容量。  
　　 推论二：  
　　网络中的最大流不超过任何割的容量。

定理二：  
　　在网络中，如果f是一个流，CUT (S,T)是一个割，且f的值等于割CUT(S,T)的 [容量][Link 2]，那么f是一个最大流， CUT(S,T)是一个最小割。

证明：  
　　令割CUT（S,T）的容量为C，所以流f的流量也为C。假设另外的任意流f1，流量为c1，根据流量不超过割的容量，则c1<=c,所以f是最大流。 假设另外的任意割CUT（S1,T1），容量为c1，根据流量不超过割的容量，所以有c1>=c,故，CUT（S,T）是最小割  \[2\]    。

结论:

在任何的网络中，最大流的值等于最小割的容量  \[1\]    。

结论一：  
　　最大流时，最小割cut(S,T)中，正向割边的流量=容量，逆向割边的流量为0。

结论二：  
　　在最小割cut(S,T)中：

1.  源点s属于S。
2.  如果i属于S，结点j满足：  
    　　有弧<i,j>,并且c \[i,j\] >f \[i,j\] ,或者有弧<i,j>,并且f \[i,j\] >0,那么j属于S。否则不是最小割。 即从s出发能找到的含有残留的点组成集合S，其余的点组成集合T。

[Link 1]: https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E6%B5%81
[500fd9f9d72a60591828dc462334349b033bbab5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D49/sign=bf0752c3af0f4bfb88d09f5d034f5824/500fd9f9d72a60591828dc462334349b033bbab5.jpg
[03087bf40ad162d9e0bc5f401adfa9ec8a13cd1f.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D11/sign=8d52f0b0da00baa1be2c43ba4610668a/03087bf40ad162d9e0bc5f401adfa9ec8a13cd1f.jpg
[Link 2]: https://baike.baidu.com/item/%E5%AE%B9%E9%87%8F