最大流最小割定理:最大流等于最小割,即max V(f) = min C(U, W)。
说明,自己的证法,如有错误请大家提出:
声明:最大流=|f|,割为=|[S,T]|
1、|[S,T]| >= |f| (易知,最大流可能比管子粗细还大?)
2、有如果有Df( |[S,T]| ) = 0 ,则一定是最大流(否则最大流的多于|[S,T]|的流量从何处流...)
3、如果当前流量已经最大,从源到汇的任意一条路径一定有饱和边(增广路法则)
4、*反证,如果对任意S,T没有Df( |[S,T]| ) = 0
取S ={源点},T={V-S};则有源点连接未饱和管道的另一端点K,然后取S={源点,K},T={V-S},则有源点连接未饱和管道的另一端点K1,然后取S={源点,K,K1},T={V-S},则有源点连接未饱和管道的另一端点K2.........当V-S = 汇点,我们发现源点,K,K1,K2,K3....汇点,为一条增广路(可能K1,K2不相连,而直接源点,K,K2)
得证。