Cuts of flow networks Cut sA cut(S, T)divides the flow G=(E, V) into 1116 15/20 two parts S and T, where S nT=o, and S∪T=E,s∈S,t∈T 4 1/4 7/7 A Net flow across a cut(s, T) is defined to be f(s, T), the capacity of(S, T)is c(S, 票c(S,T=∑u∈sy∈rc(uv) 1I14 病f(S,D=∑u∈ Svet f(uv) 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Lemma 26.5 Corollary 26.6 素f(S,T= f(S,D≤c(S,T af(S,T)=f(S,v)r-f(s, S) s Notes the definition of f and c f(s,V f(s, V)+(S-S,V) 清华大学软件学院宋恒 請华大学轼件学院宋斌包 Theorem 26.7(Max-flow min-cut 赛 Proof M1)e(2): If there exists an augmenting path p in theorem) the residual network G, then there is a induced sIf f is a flow in a flow network G=(V, E) flow f on g. hence there exists another flow f+f source s and sink t, then the following on G such that its flow is bigger than f, which is a conditions are equivalent 2(2)2(3): Because Gr contains no augmenting path, 1.f is a maximum flow in g hence there are no path from s to t in ge. Let 2.The residual network Gr contains no 3.fFc(S, T) for some cut(S, T)of G >Then the partition(S,T)is a cut, 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒 55 清华大学 软件学院 宋斌恒 25 Cuts of flow networks ÅS TÆ 1 2 3 4 s t 清华大学 软件学院 宋斌恒 26 Cut A cut (S,T) divides the flow G=(E,V) into two parts S and T, where S ∩T=φ, and S∪T=E, s∈S, t∈T. Net flow across a cut (S,T) is defined to be f(S,T), the capacity of (S,T) is c(S,T) c(S,T)=∑u ∈S,v ∈Tc(u,v) f(S,T)=∑u ∈S,v ∈T f(u,v) 清华大学 软件学院 宋斌恒 27 Lemma 26.5 f(S,T)=|f| Proof: f(S,T) = f(S,V)-f(S,S) = f(S,V) = f(s,V)+f(S-s,V) = f(s,V) = |f| 清华大学 软件学院 宋斌恒 28 Corollary 26.6 f(S,T)≤c(S,T) Notes: the definition of f and c. 清华大学 软件学院 宋斌恒 29 Theorem 26.7(Max-flow min-cut theorem) If f is a flow in a flow network G=(V,E) with source s and sink t, then the following conditions are equivalent: 1.f is a maximum flow in G 2.The residual network Gf contains no augmenting paths 3.|f|=c(S,T) for some cut (S,T) of G 清华大学 软件学院 宋斌恒 30 Proof: (1)Î(2): If there exists an augmenting path p in the residual network Gf , then there is a induced flow fp on Gf , hence there exists another flow f+fp on G such that its flow is bigger than f, which is a contradiction that f is a maximum flow on G. (2)Î(3): Because Gf contains no augmenting path, hence there are no path from s to t in Gf . Let • S={v∈V: there exists a path from s to v in Gf } • T=V-S Then the partition (S,T) is a cut