A Maximum Flow Min cut theorem for Optimizing Network

It will contain how A Maximum Flow Min cut theorem help for Optimizing Network and also use for some other purpose.

1. A Maximum Flow Min cut theorem for Optimizing Network Shethwala Ridhvesh

2. Outlines Introduction Max flow theorem Ford-Fulkerson algorithm Min cut theorem Conclusion References

3. Max Flow theorem -> A directed, weighted graph is called a (flow) network . -> Each edge has a weight and direction. -> We assume there exists a source and a sink . The flow over a network is a function f: E -> R, assigning values to each of the edges in the network which are nonnegative and less than the capacity of that edge. For each intermediate vertex, the outflow and inflow must be equal. The value of this flow is the total amount leaving the source (and thus entering the sink).

4. Ford-Fulkerson Max Flow The Ford-Fulkerson algorithm for finding the maximum flow: Construct the Residual Graph Find a path from the source to the sink with strictly positive flow. If this path exists, update flow to include it. Go to Step a. Else, the flow is maximal. The ( s,t )-cut has as S all vertices reachable from the source, and T as V - S.

5. Ford-Fulkerson Max Flow 4 1 1 2 2 1 2 3 3 1 s 2 4 5 3 t This is the original network, plus reversals of the arcs.

6. Ford-Fulkerson Max Flow 4 1 1 2 2 1 2 3 3 1 s 2 4 5 3 t This is the original network, and the original residual network.

7. 4 1 1 2 2 1 2 3 3 1 Ford-Fulkerson Max Flow Find any s-t path in G(x) s 2 4 5 3 t

8. 4 1 1 2 1 3 Ford-Fulkerson Max Flow 1 1 1 2 1 2 3 2 1 s 2 4 5 3 t

9. 4 1 1 2 1 3 Ford-Fulkerson Max Flow Find any s-t path 1 1 1 2 1 2 3 2 1 s 2 4 5 3 t

10. 4 2 1 1 1 1 2 2 1 1 1 1 3 Ford-Fulkerson Max Flow 1 1 1 1 3 2 1 s 2 4 5 3 t

11. 4 2 1 1 1 1 2 2 1 1 1 1 3 Ford-Fulkerson Max Flow 1 1 1 1 3 2 1 s 2 4 5 3 t Find any s-t path

12. 1 1 1 1 1 4 1 2 1 1 2 1 1 3 Ford-Fulkerson Max Flow 1 1 3 2 1 s 2 4 5 3 t

13. 1 1 1 1 1 4 1 2 1 1 2 2 1 1 3 Ford-Fulkerson Max Flow 1 1 3 2 1 s 2 4 5 3 t Find any s-t path

14. 1 1 1 2 1 1 1 1 4 2 2 1 1 2 2 1 Ford-Fulkerson Max Flow 1 1 3 1 1 s 2 4 5 3 t 2

15. 1 1 2 1 1 1 1 4 2 2 1 1 2 2 1 Ford-Fulkerson Max Flow 1 1 3 1 1 s 2 4 5 3 t Find any s-t path 2

16. 1 1 1 1 1 4 1 3 1 1 2 1 1 3 2 2 1 2 1 Ford-Fulkerson Max Flow 2 1 s 2 4 5 3 t 2

17. 1 1 1 1 1 4 1 3 1 1 2 1 1 3 2 2 1 2 1 Ford-Fulkerson Max Flow 2 1 s 2 4 5 3 t 2 There is no s-t path in the residual network. This flow is optimal

18. 1 1 1 1 1 4 1 3 1 1 2 1 1 3 2 2 1 2 1 Ford-Fulkerson Max Flow 2 1 s 2 4 5 3 t 2 These are the nodes that are reachable from node s. s 2 4 5 3

19. Ford-Fulkerson Max Flow 1 1 2 2 2 1 2 s 2 4 5 3 t Here is the optimal flow

20. Min cut A cut is a partition of the vertices into disjoint subsets S and T. In a flow network, the source is located in S, and the sink is located in T. The cut-set of a cut is the set of edges that begin in S and end in T. The capacity of a cut is sum of the weights of the edges beginning in S and ending in T.

21. Min cut

22. Min cut Max flow in network

23. Min cut

24. Applications - Traffic problem on road - Data Mining - Distributed Computing - Image processing - Project selection - Bipartite Matching

25. Conclusion Using this Max-flow min-cut theorem we can maximize the flow in network and can use the maximum capacity of route for optimizing network.

26. References Ford, Jr., L. R., and D. R. Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399-404. Canadian Mathematical Society. Web. 2 June,2010 Ellis L. Johnson, Committee Chair, George L. Nemhauser : Shortest paths and multicommodity network flow ,2003 FORD.L.R. AND D. R. FULKERSON 1956. Maximal Flow Through a Network. Can. J. Math. 8,399-404. Cormen , Thomas H. Introduction to Algorithms. 2nd ed. Cambridge, Massachusetts: MIT, 2001

27. THANK YOU…!!!