Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 23 Prof charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 23 Prof. Charles E. Leiserson
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. f0. 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 ∈ =
Max-flow. min-cut theorem Theorem. The following are equivalent 1. f=c(S, n) for some cut(S, T) 2. fis a maximum flow 3. f admits no augmenting paths Proof (1)→(2): Since f≤c(S, T)for any cut(S,T)(by the corollary from Lecture 22), the assumption that f=cs, T) implies that f is a maximum flow (2)=(3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f. c 2001 by Charles E Leiserson Introduction to Agorithms Day40L23.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.3 Max-flow, min-cut theorem Theorem. The following are equivalent: 1. | f | = c(S, T) for some cut (S, T). 2. f is a maximum flow. 3. f admits no augmenting paths. Proof. (1) ⇒ (2): Since | f | ≤ c(S, T) for any cut (S, T) (by the corollary from Lecture 22), the assumption that | f | = c(S, T) implies that f is a maximum flow. (2) ⇒ (3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f
Proof (continued) (3)=(1): Suppose that f admits no augmenting paths Define s=lvev: there exists a path in Gr from s to v) and let t=v-s observe that s e s and te t and thus (S, T)is a cut. Consider any vertices u E S and vE T path in g We must have cr(u, v)=0, since if cr(u, v)>0, then E S not v E T as assumed. Thus, f(u,v)=c(u, v), since cr(u,v) cu, v)f(u, v). Summing over all u E S and E ields f(S,T)=c(S, 1), and since f =f(S, T), the theorem allOWS c 2001 by Charles E Leiserson Introduction to Agorithms Day 40 L23.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.4 Proof (continued) (3) ⇒ (1): Suppose that f admits no augmenting paths. Define S = {v ∈ V : there exists a path in Gf from s to v}, and let T = V – S. Observe that s ∈ S and t ∈ T, and thus (S, T) is a cut. Consider any vertices u ∈ S and v ∈ T. We must have cf (u, v) = 0, since if cf (u, v) > 0, then v ∈ S, not v ∈ T as assumed. Thus, f(u, v) = c(u, v), since cf (u, v) = c(u, v) – f(u, v). Summing over all u ∈ S and v ∈ T yields f(S, T) = c(S, T), and since | f | = f(S, T), the theorem follows. ss uu vv S T path in Gf
Ford fulkerson max-flow algorithm Algorithm: flu,v <0 for while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow c 2001 by Charles E Leiserson Introduction to Agorithms Day40L23.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.5 Ford-Fulkerson max-flow algorithm Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p) Can be slow: ss tt 109 109 109 1 109 G:
Ford fulkerson max-flow algorithm Algorithm: flu,v <0 for while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow 0:10 0:109 0:1 0:109 0:109 c 2001 by Charles E Leiserson Introduction to Agorithms y40L236
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.6 Ford-Fulkerson max-flow algorithm Can be slow: ss tt 0:109 0:109 0:109 0:1 0:109 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p)
Ford fulkerson max-flow algorithm Algorithm: f[vl,v<0 for all u,∈ while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow 0:109 0:109 0:1 0:109 0:109 c 2001 by Charles E Leiserson Introduction to Agorithms Day40L23.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.7 Ford-Fulkerson max-flow algorithm Can be slow: ss tt 0:109 0:109 0:109 0:1 0:109 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p)
Ford fulkerson max-flow algorithm Algorithm: flu,v <0 for while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow 1:10 0:109 0:109 1:109 c 2001 by Charles E Leiserson Introduction to Agorithms Day 40 L23. 8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.8 Ford-Fulkerson max-flow algorithm Can be slow: ss tt 1:109 0:109 1:109 1:1 0:109 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p)
Ford fulkerson max-flow algorithm Algorithm: flu,v <0 for while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow 1:10 0:109 0:10 1:10 c 2001 by Charles E Leiserson Introduction to Agorithms y
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.9 Ford-Fulkerson max-flow algorithm Can be slow: ss tt 1:109 0:109 1:109 1:1 0:109 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p)
Ford fulkerson max-flow algorithm Algorithm: flu,v <0 for while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow 1:10 1:109 0:1 1:109 1:10 c 2001 by Charles E Leiserson Introduction to Agorithms Day40L23.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.10 Ford-Fulkerson max-flow algorithm Can be slow: ss tt 1:109 1:109 1:109 0:1 1:109 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p)