什么是最小割-米尼问答

的有关信息介绍如下：

所有的割中，边权值和最小的割为最小割，最大流和最小割之间的等价关系。

割：设Ci为网络N中一些弧的集合，若从N中删去Ci中的所有弧能使得从源点Vs到汇点Vt的路集为空集时，称Ci为Vs和Vt间的一个割。通俗理解，一个图或网络的割，表示一个切面或切线，将图或网络分为分别包含源点和汇点的两个子集，该切线或切面与网络相交的楞或边的集合，称为图像的割。

割(CUT)是网络中顶点的划分，它把网络中的所有顶点划分成两个顶点的集合源点S和汇点T。记为CUT(S,T)。源点：s=1;汇点：t=5。框外是容量，框内是流量。

什么是最小割

割CUT(S,T)中所有正向割边的容量和称为割的容量。不同的个的容量不同。如上图割的容量为4+4=8；割的正向流量：4+2=6 逆向割的流量：1。

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

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

结论：f= f(S,T)- f(T,S)<=f(S,T)<=割CUT（S,T）的容量。

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

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