23-Maximum Flows_ Ford-Fulkerson algorithm-26-02-2025.pptx

notesss

1. Ford Fulkerson- MaxFlow

2. What is Network Flows , Flow Networks and Maximum Flows Network flows, flow networks, and maximum flows are fundamental concepts in graph theory and optimization, particularly in the context of transportation, communication, and resource allocation problems . Network Flows : Network flows refer to the movement of resources , such as goods, information, or energy, through a network. This network can be represented as a directed graph, where Nodes represent locations or entities, Edges represent connections or pathways between them. The flow along each edge represents the quantity of resources being transferred from one node to another. Network flows are used to model various real-world scenarios, including transportation networks , communication networks , and supply chain logistics .

3. What is Network Flows, Flow Networks and Maximum Flows A flow network consists of a set of nodes (vertices) and directed edges connecting these nodes. Each edge is associated with a capacity, which represents the maximum amount of flow that can pass through it. Additionally, flow networks contain special nodes known as the source and the sink . The source is the node from which the flow originates, while the sink is the node that absorbs the flow. Flow networks are characterized by their ability to represent and solve flow optimization problems efficiently. Some real- life problems like the flow of liquids through pipes , the current through wires and delivery of goods can be modelled using flow networks. Flow Network Definition : A directed graph G =( V , E ) where V represents vertices and E represents edges. Each edge ( u , v ) ∈ E is associated with a nonnegative weight capacity c ( u , v )≥0. There are two distinguished vertices: the source s and the sink t . Every vertex v ∈ V has a path from s to t .

4. Flow Networks A flow f : V × V →R is a real- valued function satisfying certain properties. Capacity Constraint : f ( u , v )≤ c ( u , v ) for all u , v ∈ V . Skew Symmetry : f ( u , v )=− f ( v , u ) for all u , v ∈ V . Flow Conservation : Total net flow out of any vertex other than s and t is zero. For all u ∈ V −{ s , t }, the net flow out of u is zero.

5. What is Network Flows, Flow Networks and Maximum Flows Network flows, flow networks, and maximum flows are fundamental concepts in graph theory and optimization, particularly in the context of transportation, communication, and resource allocation problems. In the maximum- flow problem , we are given a flow network G with source s and sink t, and we wish to find a flow of maximum value from s to t. Maximum Flows : Maximum flows refer to the maximum amount of flow that can be sent from the source to the sink in a flow network. The maximum flow problem is a classic optimization problem that aims to determine the maximum flow value achievable in a given flow network. Mathematically, it involves finding a flow distribution that satisfies the capacity constraints of the network while maximizing the total flow from the source to the sink. Maximum flow algorithms are used to efficiently solve this problem and find the optimal flow distribution. Maximum flows have numerous applications, including network routing, capacity planning, and resource allocation in various industries. Capacity Constraint ensures that the flow through each edge does not exceed its capacity. Skew Symmetry indicates that the flow from u to v is the negative of the flow from v to u. Flow Conservation ensures that the total net flow out of any vertex (except s and t) is zero, meaning the flow into a vertex equals the flow out of it.

6. Terminology And Concepts A  flow network  if often what we call a directed graph with a flow flowing through it. The  capacity  c of an edge tells us how much flow is allowed to flow through that edge. Each edge also has a  flow  value that tells how much the current flow is in that edge.

7. The maximum flow is found by algorithms such as Ford-Fulkerson, or Edmonds-Karp, by sending more and more flow through the edges in the flow network until the capacity of the edges are such that no more flow can be sent through. Such a path where more flow can be sent through is called an  augmented path . The Ford-Fulkerson and Edmonds-Karp algorithms have implemented using something called a  residual network . The  residual network  is set up with the  residual capacities  on each edge, where the residual capacity of an edge is the capacity on that edge, minus the flow ( Resuidal Capacity= Capcity –Flow). So when flow is increased in an edge, the residual capacity is decreased with the same amount. For each edge in the residual network, there is also a  reversed edge  that points in the opposite direction of the original edge. The residual capacity of a reversed edge is the flow of the original edge. Reversed edges are important for sending flow back on an edge as part of the maximum flow algorithms.

8. Maximum flow algorithms: Ford- Fulkerson The Ford-Fulkerson algorithm, developed by L.R. Ford and Dr. R. Fulkerson in 1956, is a fundamental method for finding the maximum flow in a network. Before delving into the algorithm, it's essential to define several key concepts for better comprehension: Residual Capacity : The residual capacity of a directed edge is the difference between the edge's capacity and the current flow through it. ( capacity of the edge - current flow through the edge) If there's a flow along a directed edge from node u to v, the reversed edg e has a capacity of 0, and we denote it as f(v,u) = −f(u,v) . Residual Graph : The residual graph is derived from the original graph with the distinction that it employs residual (Remaining) capacities as edge capacities. Augmenting Path : An augmenting path is a simple path from the source (S) to the sink (T) in a residual graph, traversing edges with a capacity of 0. 4. Minimal Cut - Bottneck capacity , which decides maximum flow from source to sink through augment path.

9. Maximum flow algorithms: Ford- Fulkerson Initialize the flow of each edge e to 0. Search for an augmenting path between the source (s) and the sink (t) in the residual graph. If such a path exists, increase the flow along those edges. Repeat steps 2- 3 until no more augmenting paths exist in the residual graph. At this point, the maximum flow is achieved.

10. A flow network In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs

11. Flow Networks and Flows Flow Network is a directed graph that is used for modeling material Flow. There are two different vertices ; one is a  source  which produces material at some steady rate, and another one is sink which consumes the content at the same constant speed. The flow of the material at any mark in the system is the rate at which the element moves. Some real-life problems like the flow of liquids through pipes, the current through wires and delivery of goods can be modeled using flow networks.

12. Definition:  A Flow Network is a directed graph G = (V, E) such that For each edge (u, v) ∈ E, we associate a nonnegative weight capacity c (u, v) ≥ 0.If (u, v) ∉ E, we assume that c (u, v) = 0. There are two distinguishing points , the source s, and the sink t; For every vertex v ∈ V, there is a path from s to t containing v . Let G = (V, E) be a flow network. Let s be the source of the network, and let t be the sink. A flow in G is a real-valued function f: V x V→R such that the following properties hold:

13. Pseudocode Set flow_total = 0 Repeat until there is no path from s to t: Run Depth First Search from source vertex s to find a flow path to end vertex t Let f be the minimum capacity value on the path Add f to flow_total For each edge u → v on the path: * Decrease capacity of the edge c(u → v) by f * Increase capacity of the edge c(v → u) by f

14. Terminologies Used Augmenting Path It is the path available in a flow network. Residual Graph It represents the flow network that has additional possible flow. Residual Capacity It is the capacity of the edge after subtracting the flow from the maximum capacity.

15. Backward Flow in Ford-Fulkerson Algorithm Backward flow is an essential part of the algorithm that helps in flow adjustment when a better augmenting path is found. Key Idea of Backward Flow When an augmenting path is found, the algorithm increases the flow along that path. If a later augmenting path needs to "undo" some of the previous flow, it can push flow in the reverse direction (backward edge). This backward flow reduces the flow on a previously used edge, effectively allowing reallocation of flow through a different path.

16. How Backward Flow Works Every directed edge ( u,v ) in the residual graph has a corresponding reverse edge ( v,u ). The reverse edge allows flow to be canceled or redirected when a better augmenting path is found. If flow is pushed forward along ( u,v ), then the reverse edge ( v,u ) can be used in a future iteration to "pull" flow back. Example Consider a simple network: (A) → (B) → (C) Suppose an augmenting path A → B → C is used, and 5 units of flow are sent. Later, a new augmenting path A → C is found. To reroute flow directly from A → C , the algorithm uses the backward edge (B → A) to reduce flow on A → B. Why Backward Flow is Important It allows flow correction when a better path is found. Ensures the algorithm can adjust and reach the optimal solution. Prevents getting stuck in suboptimal flow assignments. Backward flow in the Ford-Fulkerson algorithm helps in dynamically adjusting the network flow, making it more efficient by allowing reallocation of previously assigned flow when needed.

17. Max flow =11

18. Maximum flow algorithms: Ford- Fulkerson (Example) S A B C D T S 7 inf inf 4 inf A inf 5 3 inf inf B inf inf inf inf 8 C inf inf 3 inf 5 D inf 3 inf 2 inf T inf inf inf inf inf Start with all edge flows set to 0.

19. Maximum flow algorithms: Ford- Fulkerson (Example) Search for an augmenting path. One such path is s→A→B→t with residual capacities of 7, 5, and 8. The minimum is 5, so increase the flow along the path by 5. Repeat until no more augmenting paths are found. Start with all edge flows set to 0.

20. Maximum flow algorithms: Ford- Fulkerson (Example) Search for an augmenting path. One such path is s→A→B→t with residual capacities of 7, 5, and 8. The minimum is 5, so increase the flow along the path by 5. Start with all edge flows set to 0. Look for other possible augmenting paths. For example, s→D→C→t with residual capacities of 4, 2, and 5, with 2 being the minimum. Increase the flow by 2 along this path. Repeat until no more augmenting paths are found.

21. Maximum flow algorithms: Ford- Fulkerson (Example) Continue searching for augmenting paths, ensuring that previously saturated edges (such as A→B and D→C are flow has reached their maximum capacity ) are not included. For instance, s→D→A→C→t has residual capacities of 2, 3, 3, and 3, with 2 being the minimum. Increase the flow by 2 along this path. Repeat until no more augmenting paths are found.

22. Maximum flow algorithms: Ford- Fulkerson (Example) Continue searching for augmenting paths, ensuring that previously saturated edges (such as A→B and D→C are flow has reached their maximum capacity ) are not included. For instance, s→A→C→t has residual capacities of 1, 1, and 1, with 1 being the minimum. Increase the flow by 1 along this path. Now there are no more augmenting paths possible in the network

23. Maximum flow algorithms: Ford- Fulkerson (Example) The maximum flow is determined by the total flow going out of the source or coming into the sink. In this case, it is 6+4=5+5=10.

24. The following image shows a flow network. The first value of each edge represents the flow, which is initially 0, and the second value represents the capacity. Flow network To demonstrate the method. We use the same flow network as above. Initially we start with a flow of 0.

25. EXAMPLE

26. The capacity for forward and reverse paths are considered separately.

27. Example 3

28. s t v1 v2 v4 v3 13 16 12 20 14 4 10 4 9 s t v1 v2 v4 v3 13 4/16 4/12 20 4/14 4/4 10 4 4/9 7 7 Example:

29. s t v1 v2 v4 v3 13 12 8 20 10 4 10 4 5 4 7 4 4 s t v1 v2 v4 v3 13 11/16 7/20 11/14 4/4 7/10 4 4/9 7/7 4/12 4 Reverse flow from V3 ->V1 =7+4 =11

30. s t v1 v2 v4 v3 13 5 8 13 3 4 3 11 5 4 7 11 11 4 7 s t v1 v2 v4 v3 8/13 11/16 15/20 11/14 4/4 10 1/4 4/9 7/7 12/12 Reverse flow from V3 ->V1 =7+4 =11 Minimal( 13,11,8,13 ) = 8

31. s t v1 v2 v4 v3 8 5 12 5 3 4 11 3 5 4 7 11 15 5 11 s v1 v2 v4 v3 12/13 11/16 11/14 4/4 10 1/4 9 7/7 12/12 t 19/20

32. s t v1 v2 v4 v3 1 5 12 1 3 4 11 3 9 7 11 19 12 11 Augmented Path Bottle neck Capacity S->v1->v2->v3->v4->t 4 S->v1->v3->v4->v2->t 7 S->v3->v1->v2->t 8 S->v3->v2->t MAXIMUM FLOW CAPACITY = 23 4

33. Psuedocode

34. Complexity

35. Max-Flow Problem source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 Task : Maximize the flow from the sink to the source such that 1) The flow it conserved for each node 2) The flow for each pipe does not exceed the capacity

36. Max-Flow Problem source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3

37. Max-Flow Problem source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 flow from the source capacity flow from node i to node j conservation of flow set of edges set of nodes

38. Max-Flow Problem source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End

39. Max-Flow Problem source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End

40. Max-Flow Problem source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 3

41. Max-Flow Problem source sink 9 5 6-3 8-3 4 2+3 2 2 5-3 3-3 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 3 +3

42. Max-Flow Problem source sink 9 5 3 5 4 5 2 2 2 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 3 3

43. Max-Flow Problem source sink 9 5 3 5 4 5 2 2 2 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 3 3

44. Max-Flow Problem source sink 9 5 3 5 4 5 2 2 2 5 5 3 1 1 6 2 3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 6 3

45. Max-Flow Problem source sink 9-3 5 3 5-3 4 5 2 2 2 5 5 3-3 1 1 6 2 3-3 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 6 3 +3 +3

46. Max-Flow Problem source sink 6 5 3 2 4 5 2 2 2 5 5 1 1 6 2 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 6 3 3 3

47. Max-Flow Problem source sink 6 5 3 2 4 5 2 2 2 5 5 1 1 6 2 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 6 3 3 3

48. Max-Flow Problem source sink 6 5 3 2 4 5 2 2 2 5 5 1 1 6 2 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 11 3 3 3

49. Max-Flow Problem source sink 6-5 5-5 3 2 4 5 2 2 2 5-5 5-5 1+5 1 6 2+5 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 11 3 3 3

50. Max-Flow Problem source sink 1 3 2 4 5 2 2 2 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 11 3 3 3

51. Max-Flow Problem source sink 1 3 2 4 5 2 2 2 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 11 3 3 3

52. Max-Flow Problem source sink 1 3 2 4 5 2 2 2 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 13 3 3 3

53. Max-Flow Problem source sink 1 3 2-2 4 5 2-2 2-2 2-2 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 13 3 3 3 +2 +2

54. Max-Flow Problem source sink 1 3 4 5 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 13 3 3 3 2 2

55. Max-Flow Problem source sink 1 3 4 5 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 13 3 3 3 2 2

56. Max-Flow Problem source sink 1 3 4 5 6 1 6 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 15 3 3 3 2 2

57. Max-Flow Problem source sink 1 3-2 4-2 5 6 1 6-2 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 15 3 3 3+2 2 2-2 +2

58. Max-Flow Problem source sink 1 1 5 6 1 4 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 15 3 3 5 2 2 2

59. Max-Flow Problem source sink 1 1 5 6 1 4 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 15 3 3 5 2 2 2

60. Max-Flow Problem source sink 1 1 5 6 1 4 7 Ford & Fulkerson algorithm (1956) Find the path from source to sink While (path exists) flow += maximum capacity in the path Build the residual graph (“subtract” the flow) Find the path in the residual graph End flow = 15 3 3 5 2 2 2

61. Max-Flow Problem source sink 1 1 5 6 1 4 7 Ford & Fulkerson algorithm (1956) Why is the solution globally optimal ? flow = 15 3 3 5 2 2 2

62. Max-Flow Problem source sink 1 1 5 6 1 4 7 Ford & Fulkerson algorithm (1956) Why is the solution globally optimal ? 1. Let S be the set of reachable nodes in the residual graph flow = 15 3 3 5 2 2 2 S

63. Max-Flow Problem Ford & Fulkerson algorithm (1956) Why is the solution globally optimal ? 1. Let S be the set of reachable nodes in the residual graph 2. The flow from S to V - S equals to the sum of capacities from S to V – S source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 S

64. Max-Flow Problem Ford & Fulkerson algorithm (1956) Why is the solution globally optimal ? 1. Let S be the set of reachable nodes in the residual graph 2. The flow from S to V - S equals to the sum of capacities from S to V – S 3. The flow from any A to V - A is upper bounded by the sum of capacities from A to V – A source sink 9 5 6 8 4 2 2 2 5 3 5 5 3 1 1 6 2 3 A

65. Max-Flow Problem flow = 15 Ford & Fulkerson algorithm (1956) Why is the solution globally optimal ? 1. Let S be the set of reachable nodes in the residual graph 2. The flow from S to V - S equals to the sum of capacities from S to V – S 3. The flow from any A to V - A is upper bounded by the sum of capacities from A to V – A 4. The solution is globally optimal source sink 8/9 5/5 5/6 8/8 2/4 0/2 2/2 0/2 5/5 3/3 5/5 5/5 3/3 0/1 0/1 2/6 0/2 3/3 Individual flows obtained by summing up all paths

66. Max-Flow Problem flow = 15 Ford & Fulkerson algorithm (1956) Why is the solution globally optimal ? 1. Let S be the set of reachable nodes in the residual graph 2. The flow from S to V - S equals to the sum of capacities from S to V – S 3. The flow from any A to V - A is upper bounded by the sum of capacities from A to V – A 4. The solution is globally optimal source sink 8/9 5/5 5/6 8/8 2/4 0/2 2/2 0/2 5/5 3/3 5/5 5/5 3/3 0/1 0/1 2/6 0/2 3/3