Page 1 1 CSE 421 Algorithms g Richard Anderson Lecture 22 Network Flow Review • Network flow definitions • Flow examples • Augmenting Paths • Residual Graph • Ford Fulkerson Algorithm •Cuts • Maxflow-MinCut Theorem Network Flow Definitions • Flowgraph: Directed graph with distinguished vertices s (source) and t (sink) • Capacities on the edges, c(e) >= 0 • Problem, assign flows f(e) to the edges such Problem, assign flows f(e) to the edges such that: – 0 <= f(e) <= c(e) – Flow is conserved at vertices other than s and t • Flow conservation: flow going into a vertex equals the flow going out – The flow leaving the source is a large as possible Find a maximum flow a d g 5/5 20/20 20/20 20/20 20/20 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/5 0/5 0/5 0/5 0/20 Residual Graph • Flow graph showing the remaining capacity • Flow graph G, Residual Graph G R – G: edge e from u to v with capacity c and flow f G d’f t ith it f – G R : edge e’ from u to v with capacity c – f –G R : edge e’’ from v to u with capacity f Residual Graph u 15/20 15/30 0/10 u 510 15 s t v 20/20 15/30 5/10 s t v 15 5 20 15 5 Page 2 1 CSE 421 Algorithms g Richard Anderson Lecture 22 Network Flow Review • Network flow definitions • Flow examples • Augmenting Paths • Residual Graph • Ford Fulkerson Algorithm •Cuts • Maxflow-MinCut Theorem Network Flow Definitions • Flowgraph: Directed graph with distinguished vertices s (source) and t (sink) • Capacities on the edges, c(e) >= 0 • Problem, assign flows f(e) to the edges such Problem, assign flows f(e) to the edges such that: – 0 <= f(e) <= c(e) – Flow is conserved at vertices other than s and t • Flow conservation: flow going into a vertex equals the flow going out – The flow leaving the source is a large as possible Find a maximum flow a d g 5/5 20/20 20/20 20/20 20/20 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/5 0/5 0/5 0/5 0/20 Residual Graph • Flow graph showing the remaining capacity • Flow graph G, Residual Graph G R – G: edge e from u to v with capacity c and flow f G d’f t ith it f – G R : edge e’ from u to v with capacity c – f –G R : edge e’’ from v to u with capacity f Residual Graph u 15/20 15/30 0/10 u 510 15 s t v 20/20 15/30 5/10 s t v 15 5 20 15 5 2 Build the residual graph s d e g h t 3/5 2/4 3/3 1/5 1/5 1/1 3/3 2/5 1/1 s d e g h t Residual graph: Augmenting Path Lemma • Let P = v 1 , v 2 , …, v k be a path from s to t with minimum capacity b in the residual graph. • b units of flow can be added along the path P in the flow graph. gp u s t v 15/20 20/20 15/30 0/10 5/10 u s t v 5 15 10 5 20 15 15 5 Proof • Add b units of flow along the path P • What do we need to verify to show we have a valid flow after we do this? – – Ford-Fulkerson Algorithm (1956) while not done Construct residual graph G R Find an s-t path P in G R with capacity b > 0 Add b units along in G If the sum of the capacities of edges leaving S is at most C, then the algorithm takes at most C iterations Cuts in a graph • Cut: Partition of V into disjoint sets S, T with s in S and t in T. • Cap(S,T): sum of the capacities of edges from S to T Fl (S T) t fl t f S • Flow(S,T): net flow out of S – Sum of flows out of S minus sum of flows into S • Flow(S,T) <= Cap(S,T) What is Cap(S,T) and Flow(S,T) a d g 5/5 20/20 20/20 20/20 20/20 S={s, a, b, e, h}, T = {c, f, i, d, g, t} 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/20 0/5 0/10 Page 3 1 CSE 421 Algorithms g Richard Anderson Lecture 22 Network Flow Review • Network flow definitions • Flow examples • Augmenting Paths • Residual Graph • Ford Fulkerson Algorithm •Cuts • Maxflow-MinCut Theorem Network Flow Definitions • Flowgraph: Directed graph with distinguished vertices s (source) and t (sink) • Capacities on the edges, c(e) >= 0 • Problem, assign flows f(e) to the edges such Problem, assign flows f(e) to the edges such that: – 0 <= f(e) <= c(e) – Flow is conserved at vertices other than s and t • Flow conservation: flow going into a vertex equals the flow going out – The flow leaving the source is a large as possible Find a maximum flow a d g 5/5 20/20 20/20 20/20 20/20 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/5 0/5 0/5 0/5 0/20 Residual Graph • Flow graph showing the remaining capacity • Flow graph G, Residual Graph G R – G: edge e from u to v with capacity c and flow f G d’f t ith it f – G R : edge e’ from u to v with capacity c – f –G R : edge e’’ from v to u with capacity f Residual Graph u 15/20 15/30 0/10 u 510 15 s t v 20/20 15/30 5/10 s t v 15 5 20 15 5 2 Build the residual graph s d e g h t 3/5 2/4 3/3 1/5 1/5 1/1 3/3 2/5 1/1 s d e g h t Residual graph: Augmenting Path Lemma • Let P = v 1 , v 2 , …, v k be a path from s to t with minimum capacity b in the residual graph. • b units of flow can be added along the path P in the flow graph. gp u s t v 15/20 20/20 15/30 0/10 5/10 u s t v 5 15 10 5 20 15 15 5 Proof • Add b units of flow along the path P • What do we need to verify to show we have a valid flow after we do this? – – Ford-Fulkerson Algorithm (1956) while not done Construct residual graph G R Find an s-t path P in G R with capacity b > 0 Add b units along in G If the sum of the capacities of edges leaving S is at most C, then the algorithm takes at most C iterations Cuts in a graph • Cut: Partition of V into disjoint sets S, T with s in S and t in T. • Cap(S,T): sum of the capacities of edges from S to T Fl (S T) t fl t f S • Flow(S,T): net flow out of S – Sum of flows out of S minus sum of flows into S • Flow(S,T) <= Cap(S,T) What is Cap(S,T) and Flow(S,T) a d g 5/5 20/20 20/20 20/20 20/20 S={s, a, b, e, h}, T = {c, f, i, d, g, t} 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/20 0/5 0/10 3 Minimum value cut u 40 10 s t v 40 10 10 Find a minimum value cut 6 6 5 8 s t 10 7 3 36 2 4 5 8 5 4 8 MaxFlow – MinCut Theorem • There exists a flow which has the same value of the minimum cut • Proof: Consider a flow where the residual graph has no s-t path with positive capacity pp py • Let S be the set of vertices in G R reachable from s with paths of positive capacity s t Let S be the set of vertices in G R reachable from s with paths of positive capacity s t u v S T What can we say about the flows and capacity between u and v? Max Flow - Min Cut Theorem • Ford-Fulkerson algorithm finds a flow where the residual graph is disconnected, hence FF finds a maximum flow. • If we want to find a minimum cut, we begin by looking for a maximum flow. Performance • The worst case performance of the Ford- Fulkerson algorithm is horrible u s t v 1000 1000 1 1000 1000 Page 4 1 CSE 421 Algorithms g Richard Anderson Lecture 22 Network Flow Review • Network flow definitions • Flow examples • Augmenting Paths • Residual Graph • Ford Fulkerson Algorithm •Cuts • Maxflow-MinCut Theorem Network Flow Definitions • Flowgraph: Directed graph with distinguished vertices s (source) and t (sink) • Capacities on the edges, c(e) >= 0 • Problem, assign flows f(e) to the edges such Problem, assign flows f(e) to the edges such that: – 0 <= f(e) <= c(e) – Flow is conserved at vertices other than s and t • Flow conservation: flow going into a vertex equals the flow going out – The flow leaving the source is a large as possible Find a maximum flow a d g 5/5 20/20 20/20 20/20 20/20 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/5 0/5 0/5 0/5 0/20 Residual Graph • Flow graph showing the remaining capacity • Flow graph G, Residual Graph G R – G: edge e from u to v with capacity c and flow f G d’f t ith it f – G R : edge e’ from u to v with capacity c – f –G R : edge e’’ from v to u with capacity f Residual Graph u 15/20 15/30 0/10 u 510 15 s t v 20/20 15/30 5/10 s t v 15 5 20 15 5 2 Build the residual graph s d e g h t 3/5 2/4 3/3 1/5 1/5 1/1 3/3 2/5 1/1 s d e g h t Residual graph: Augmenting Path Lemma • Let P = v 1 , v 2 , …, v k be a path from s to t with minimum capacity b in the residual graph. • b units of flow can be added along the path P in the flow graph. gp u s t v 15/20 20/20 15/30 0/10 5/10 u s t v 5 15 10 5 20 15 15 5 Proof • Add b units of flow along the path P • What do we need to verify to show we have a valid flow after we do this? – – Ford-Fulkerson Algorithm (1956) while not done Construct residual graph G R Find an s-t path P in G R with capacity b > 0 Add b units along in G If the sum of the capacities of edges leaving S is at most C, then the algorithm takes at most C iterations Cuts in a graph • Cut: Partition of V into disjoint sets S, T with s in S and t in T. • Cap(S,T): sum of the capacities of edges from S to T Fl (S T) t fl t f S • Flow(S,T): net flow out of S – Sum of flows out of S minus sum of flows into S • Flow(S,T) <= Cap(S,T) What is Cap(S,T) and Flow(S,T) a d g 5/5 20/20 20/20 20/20 20/20 S={s, a, b, e, h}, T = {c, f, i, d, g, t} 0/5 0/5 0/5 0/5 s b c f e h i t 15/25 25/30 20/20 5/5 20/20 0/5 20/20 15/20 10/10 20/20 5/5 30/30 0/20 0/5 0/10 3 Minimum value cut u 40 10 s t v 40 10 10 Find a minimum value cut 6 6 5 8 s t 10 7 3 36 2 4 5 8 5 4 8 MaxFlow – MinCut Theorem • There exists a flow which has the same value of the minimum cut • Proof: Consider a flow where the residual graph has no s-t path with positive capacity pp py • Let S be the set of vertices in G R reachable from s with paths of positive capacity s t Let S be the set of vertices in G R reachable from s with paths of positive capacity s t u v S T What can we say about the flows and capacity between u and v? Max Flow - Min Cut Theorem • Ford-Fulkerson algorithm finds a flow where the residual graph is disconnected, hence FF finds a maximum flow. • If we want to find a minimum cut, we begin by looking for a maximum flow. Performance • The worst case performance of the Ford- Fulkerson algorithm is horrible u s t v 1000 1000 1 1000 1000 4 Better methods of finding augmenting paths • Find the maximum capacity augmenting path –O(m 2 log(C)) time algorithm for network flow Find the shortest augmenting path • Find the shortest augmenting path –O(m 2 n) time algorithm for network flow • Find a blocking flow in the residual graph – O(mnlog n) time algorithm for network flowRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!