Recall from lecture 22 Flow value: f=f(s, v) Cut: Any partition(, T)of y such that s E S andt∈T Lemma. f=f(s, n) for any cut(S, T) Corollary. f<c(s, n) for any cut(S, T) Residual graph: The graph G-V,Er)with strictly positive residual capacities cr(u, v) c(l,y)-f(l,y)>0. Augmenting path: Any path from s to t in Gr Residual capacity of an augmenting path Cy(p)=min (cr(u, v) (u, vEp c 2001 by Charles E Leiserson Introduction to Algorithms Day40L23.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.2 Recall from Lecture 22 • Flow value: | f | = f(s, V). • Cut: Any partition (S, T) of V such that s ∈ S and t ∈ T. • Lemma. | f | = f(S, T) for any cut (S, T). • Corollary. | f | ≤ c(S, T) for any cut (S, T). • Residual graph: The graph Gf = (V, Ef ) with strictly positive residual capacities cf (u, v) = c(u, v) – f(u, v) > 0. • Augmenting path: Any path from s to t in Gf . • Residual capacity of an augmenting path: ( ) min { ( , )} ( , ) c p c u v f u v p f ∈ =