Max-Flow Min-Cut Explained: Ford-Fulkerson, Edmonds-Karp, Bipartite Matching & DAG Path Cover

A complete walkthrough of flow networks and the Max-Flow Min-Cut Theorem, with step-by-step simulations of the Ford-Fulkerson and Edmonds-Karp algorithms and two classic applications: maximum bipartite matching and minimum path cover in a DAG. Algorithm Design & Analysis — Group Presentation Presented by: • Md. Perves (Reg. No. 2024331108) — Foundations of flow networks • Rizwan Ahmad (Reg. No. 2024331078) — Theorem, algorithms & complexity • Fiaz Nabi (Reg. No. 2024331106) — Applications & conclusion What you'll learn: • What a flow network is: source, sink, capacity, flow, conservation • Residual graphs, reverse edges, augmenting paths and bottlenecks • s-t cuts and why max flow = min cut • Ford-Fulkerson, simulated step by step with a min-cut certificate • Edmonds-Karp (BFS shortest paths) and why it runs in O(VE²) • Why Ford-Fulkerson is O(E·F) and pseudo-polynomial • Maximum bipartite matching via max flow • Minimum vertex-disjoint path cover in a DAG = |V| − |M| Chapters: 0:00 Introduction 0:33 How much can a network carry? 1:30 Applications and our plan 2:22 The flow network model 3:27 Flow, flow value and the two rules 4:36 Residual capacity 5:38 Why we need reverse edges 6:48 Augmenting paths and the bottleneck 7:51 s-t cuts and their capacity 9:13 The Max-Flow Min-Cut Theorem 10:10 Why the theorem holds 11:13 The Ford-Fulkerson method 12:09 Ford-Fulkerson iteration 1 12:50 Ford-Fulkerson iteration 2 13:33 Ford-Fulkerson iteration 3 14:06 Termination and the min-cut certificate 15:03 Edmonds-Karp: shortest paths with BFS 16:01 Edmonds-Karp walkthrough 16:56 Where the running times come from 17:54 Comparison: why path choice matters 18:50 Maximum bipartite matching 19:51 Reducing matching to max flow 21:02 Matching example: reverse edges reassign 22:14 Minimum path cover in a DAG 23:07 From path cover to matching 24:12 Path cover worked example 25:18 Conclusion #Algorithms #MaxFlow #FordFulkerson #EdmondsKarp #GraphTheory #DAA