Ford-Fulkerson AlgorithmPowerPoint PresentationResidual NetworkSlide 4Augmented PathSlide 6Final max flowThe corresponding Residual NetworkAnalysis of the Ford Fulkerson algorithm Running time (arbitrary choice of p)Slide 10Slide 11Edmonds-Karp AlgorithmSlide 13Using Edmond-Karp algorithmSlide 15Slide 16Edmonds-Karp Algorithm – Theorem 1Max Flow Min Cut TheoremSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24How do we know when a flow is optimal?Minimum Cut ProblemCutsSlide 28Slide 29Slide 30Slide 31Flow value lemmaWeak Duality theoremMax-Flow Min-Cut TheoremSlide 35Slide 36Slide 37Slide 38Ford-Fulkerson AlgorithmAny more paths to Augument ? – Let us see the residual NetworkResidual Network•The residual network has the same vertices as the original network, and one or two edges for each edge in the original. •More specifically, –if the flow along the edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the difference between the capacity and the flow (this is called the residual capacity), –and if the flow is positive there is a backward edge y-x with a capacity equal to the flow on x-y.Residual Network•the residual network:Augmented Path•Let's consider the only path from X to Y here: X_A_C_B_D_E_Y. –Note that this is not a path in the directed graph, because C_B is walked in the opposite way. –We'll use this path in order to increase the total flow in the original network.Augmented Path–We'll "push" flow on each of the edges, –except for C_B which we will use in order to "cancel" flow on B_C. –The amount by which this operation can be performed is limited by the capacities of all edges along the path (as shown in Figure 3b). –Once again we take the minimum, to conclude that this path also has capacity 1.Final max flowThe corresponding Residual NetworkWe are left with the following residual network where a path between the source and the sink doesn't exist:Analysis of the Ford Fulkerson algorithmRunning time (arbitrary choice of p)(1) The augmenting path is chosen arbitrarily and all capacities are integersConsequencies of an arbitrarily choice:Example if |f*| is large: tv2v1s1,000,0001,000,0001,000,0001,000,0001running time: O ( |E| |fmax| )with fmax as maximum flowAnalysis of the Ford Fulkerson algorithmRunning time (arbitrary choice of p)(1) The augmenting path is chosen arbitrarily and all capacities are integersConsequencies of an arbitrarily choice:Example if |f*| is large: tv2v1s1 / 1,000,0001,000,0001,000,0001 / 1,000,0001 / 1tv2v1s999,9991,000,0001,000,000999,9991residual network Gf 11running time: O ( |E| |fmax| )with fmax as maximum flowAnalysis of the Ford Fulkerson algorithmRunning time (arbitrary choice of p)(1) The augmenting path is chosen arbitrarily and all capacities are integersConsequencies of an arbitrarily choice:Example if |f*| is large: tv2v1s1 / 1,000,0001 / 1,000,0001 / 1,000,0001 / 1,000,0001tv2v1s999,999999,999999,999999,9991residual network Gf 1111running time: O ( |E| |fmax| )with fmax as maximum flowEdmonds-Karp Algorithm•The Ford-Fulkerson algorithm does not specify which alternating path to use if there is more than one. •In 1972, Jack Edmonds and Richard Karp analyzed two natural heuristics for choosing the path.Edmonds-Karp Algorithm•The first is essentially a greedy algorithm:–Choose the augmenting path with largest bottleneck value.–Choose the augmenting path with fewest edges.Using Edmond-Karp algorithmComplete in 2 itrationstv2v1s1,000,0001,000,0001,000,0001,000,0001Try the previous example also.15Edmonds-Karp Algorithm•The first is essentially a greedy algorithm:–Choose the augmenting path with largest bottleneck value.–Choose the augmenting path with fewest edges.Edmonds-Karp Algorithm – Theorem 1•If among the possible augmenting paths in the residual graph a shortest path is chosen in every iteration, then the algorithm reaches the maximum flow after at most nm/4 iterations, where n is the number of nodes and m is the number of edges in the graph.Max Flow Min Cut Theorem•The value of the maximum flow from s to d is equal to the minimum capacity of any cut which separates d from s.•Since no more flow can be pushed through any cut than its capacity, therefore, the total s → d flow can never be larger than the capacity of any s→d cut (a cut that separates d from s). That is, for any feasible value F of the s→d flow and for any s→d cut with capacity C F ≤ Calways holds.•The nice thing is that if we maximize the lefthand-side and minimize the righthand-side, then we get precise equality. In other words, whatever is not obviously excluded by the capacity limitations, can actually be achieved. There is no gap here between the theoretically possible and the practically achievable.•Yet another important result is about the integrality of the maximum flow.–Theorem: If all capacities are integers, then there exists a maximum flow in which the value of the flow on each edge is an integer (and, therefore, the total flow is also integer). Such an integer flow can also be efficiently foundby the Ford-Fulkerson or Edmonds-Karp algorithms.•Note: This integrality theorem makes it possible to use maximum flow computations for solving graph optimization problems. Examples are the maximum number of independent paths or the maximum matching problem in bipartite graphs. See details in the slide set entitled "Application of Maxi-mum Flow to Other Optimization Problems".•Lemma: At each iteration all residual capacities are integral.•Proof. It is true at the beginning. Assume it is true after the first k-1 augmentations, and consider augmentation k along path P. The residual capacity Δ of P is the smallest residual capacity on P, which is integral. After updating, we modify residual capacities by 0, or Δ, and thus residual capacities stay integral.•Theorem. The Ford-Fulkerson Algorithm is finite–Proof. The capacity of each augmenting path is at least 1.–The augmentation reduces the residual capacity of some arc (s, j) and does not increase the residual capacity of (s, i) for any i. –So, the sum of the residual capacities of arcs out of s keeps decreasing, and is bounded below by 0.–Number of augmentations is O(nU), where U is the largest capacity in the network.How do we know when a flow is optimal?•METHOD 1. There is no augmenting path in the residual network.•Method 2: Cut Duality TheoryFlow network.Abstraction for material flowing
View Full Document
Unlocking...