定義 f(X,Y) = Σ Σ f(u,v)
u in X v in Y
c(X,Y) = Σ Σ c(u,v)
u in X v in Y
f(u,v)是流量, c(u,v)是容量, |f|為最大流的值
令 S,T 是 V 的一個分割且 s in S, t in T
c(S,T) = Σ Σ c(u,v)
u in S v in T
>= Σ Σ f(u,v)
u in S v in T
= f(S,T)
= |f|
所以 c(S,T) >= f(S,T) = |f|
而假若我們取 S = s + { v | 殘餘流量網路 Gf 中有一條 s 到 v 的路徑}
則此時等號成立
(若等號不成立->此時的|f|非最大流(矛盾))
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.32.167