Maximal Flow Problem

Presentation slide on Maximum flow problem

1. Presentation on Maximal Flow Problem Presented by : Saroj Kumar Banjara NOU Roll No. 76155026(M.Phil.)

2. Maximal Flow Problem( Frod Fulkerson Rule) Find the maximum flow throuth the given network using Ford Fulkerson algorithm. 1 7 4 6 3 5 2 2 2 10 3 3 7 4 10 5 7 1 2

3. The ford Fulkerson method is used for solving maximum flow problem.It is a popular method for finding the maximum flow Basic Terms: Source vertex Sink vertex Capacity and bottle neck capacity Flow Augumenting path Residual capacity 1 7 4 6 3 5 2 2 2 10 3 3 4 10 5 7 1 2

4. Source :The source vertex has all outward edge,no inward edge Sink : Sink will have all inward edge, no outward edge Bottleneck capacity : Bottle neck capacity of the path is the minimum capacity of any edge on the path Flow: Augumenting path: Residual capacity: Every edge of a residual graph has a value called residual capacity, which is equal to original capacity minus current flow. 5 8 Capacity Flow

5. Solution 1 7 4 6 3 5 2 0/2 0/2 0/10 0/3 0/3 0/7 0/4 0/10 0/5 0/7 0/1 0/2 Source sink

6. 1 1 7 4 6 3 5 2 0/2 0/2 0/10 0/3 0/3 0/7 0/4 5/10 5/5 5/7 0/1 0/2 Source Flow = 5 Augmenting path Bottleneck capacity 1-2-5-7 5

7. 1 1 7 4 6 3 5 2 0/2 0/2 4/10 0/3 0/3 4/7 4/4 5/10 5/5 5/7 0/1 0/2 Source Flow = 5+4 Augmenting path Bottleneck capacity 1-2-5-7 5 1-3-6-7 4

8. 1 1 7 4 6 3 5 2 0/2 0/2 4/10 2/3 2/3 4/7 4/4 7/10 5/5 7/7 0/1 0/2 Source Flow = 5+4+2 Augmenting path Bottleneck capacity 1-2-5-7 5 1-3-6-7 4 1-2-4-5-7 2

9. 1 1 7 4 6 3 5 2 0/2 1/2 5/10 3/3 2/3 4/7 4/4 8/10 5/5 7/7 0/1 0/2 Source Flow = 5+4+2+1 Augmenting path Bottleneck capacity 1-2-5-7 5 1-3-6-7 4 1-2-4-5-7 2 1-3-4-5-7 1 Maximum flow = 12