定理一:
  如果f是网络中的一个流,CUT(S,T)是任意一个割,那么f的值等于正向割边的流量与负向割边的流量之差。
证明:
  设X和Y是网络中的两个顶点集合,用f(X,Y)表示从X中的一个顶点指向Y的一个顶点的所有弧(弧尾在X中,弧头在Y中: )的流量和。只需证明:f=f(S,T)-f(T,S) 即可。
推论一:
  如果f是网络中的一个流,CUT(S,T)是一个割,那么f的值不超过割CUT(S,T)的容量。
  推论二:
  网络中的最大流不超过任何割的容量。
定理二:
  在网络中,如果f是一个流,CUT (S,T)是一个割,且f的值等于割CUT(S,T)的容量,那么f是一个最大流, CUT(S,T)是一个最小割。
证明:
  令割CUT(S,T)的容量为C,所以流f的流量也为C。假设另外的任意流f1,流量为c1,根据流量不超过割的容量,则c1<=c,所以f是最大流。 假设另外的任意割CUT(S1,T1),容量为c1,根据流量不超过割的容量,所以有c1>=c,故,CUT(S,T)是最小割 。

02-16 07:33