作者suhorng ( )
站内Math
标题Re: [图论] 求定理和证明解释
时间Sat Jan 8 22:27:18 2011
定义 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