最大流最小割定理:最大流等于最小割,即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)
得證。