Lemma 26.2 s Let g=(v,E)be a flow network with source 113 sink t, and f be a flow in G. Let Gr be the residual network of g induced(诱导)by f Let f be a flow in g. then f+f is a fl in g with fIfI+IfI 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Augmenting paths(增广路径) 素 Skew symmetry a Given a flow network G=(V,E)and a flow f s Capacity constrain an augmenting path p is a simple path from 成 Value of f+f s to t m Residual capacity of an augmenting path p cdu,v): (u, v) is on pi 清华大学软件学院宋恒 請华大学轼件学院宋斌包 low f, induced by p is a flow in g and its value ater than f sThe following function fp 什fHfF (p) If (u, v)is on p fp(u,v)=-c,(p)If(v, u)is onp 0 other wise 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒4 清华大学 软件学院 宋斌恒 19 1 3 2 4 s t 清华大学 软件学院 宋斌恒 20 Lemma 26.2 Let G=(V,E) be a flow network with source s and sink t, and f be a flow in G. Let Gf be the residual network of G induced(诱导) by f. Let f’ be a flow in Gf , then f+f’ is a flow in G with |f+f’|=|f|+|f’| 清华大学 软件学院 宋斌恒 21 Proof. Skew symmetry Capacity constrain Value of f+f’ 清华大学 软件学院 宋斌恒 22 Augmenting paths(增广路径) Given a flow network G=(V,E) and a flow f, an augmenting path p is a simple path from s to t. Residual capacity of an augmenting path p is given by cf (p)=min{cf (u,v): (u,v) is on p} 清华大学 软件学院 宋斌恒 23 Flow fp induced by p The following function fp: is a flow in Gf . other wise If (v,u) is on p If (u, v) is on p 0 ( ) ( ) ( , ) ⎪ ⎩ ⎪ ⎨ ⎧ = − c p c p f u v f f p 清华大学 软件学院 宋斌恒 24 f+fp is a flow in G and its value is greater than f. | f+fp |=| f |+| fp |>| f|