最大流最小割定理个人理解

1.首先很重要的一个引理：任意割的净流量都是相同的，且与流的值相等。 直观上很容易理解， 个人证明： 设流网络G=(V,E) 假如一割净流量与流的值不等，那肯定有剩余的流从源点经由网络流之外的路线到达汇点，那么表示对于u,v∉E,存在f(u,v)≠0且-f(v,u)≠0。 根据流网络定义对于u,v∉E，有f(u,v)=f(v,u)=0,与假设矛盾,所以任意割的净流量等于流的值，那么也表明任意割的净流量都是相同的。 算导上也有个非常好的证明： 设f是源点为s,汇点为t的的网络流G中的一个流。并且(S,T)是G的一个割。 则有： f(S,T)=f(S,V)-f(S,S) =f(S,V) =f(s,V)+f(S-s,V) =f(s,V) =|f| 2.然后根据推论26.6，对一个流网络G的任意流来说，其值的上界为G的任意割的容量，可以推出对于最大流|f|一定不大于G中最小割容量。 3. [Image unavailable: 最大流最小割定理.png] 1）\(\Rightarrow\) 2)很容易，不说了。 2）\(\Rightarrow\) 3)很重要，证明了在最大流情况下，最大流|f|=f(S,T)=c(S,T)。（可以看出c(S,T)一定为最小割，具体原因看上面2.) 之后可以很容易得到1）\(\Rightarrow\) 3)，也就是最大流的值等于最小割的容量这个重要定理，反过去证明非常容易，见上面证明3）。