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!