Network Flow

Discrete Math · Axiom Academy

LESSON Network Flow: Max Flow Problem Understanding flow networks, the Ford-Fulkerson algorithm, and the powerful min-cut max-flow theorem A source vertex s (where flow originates) A sink vertex t (where flow terminates) Each edge (u, v) has a capacity c(u, v) ≥ 0 A flow f(u, v) on each edge satisfying constraints Capacity Constraint: Flow cannot exceed capacity: f(u, v) ≤ c(u, v) Conservation: Flow in = Flow out (except at source and sink) The key insight of Ford-Fulkerson: if we can find a path from s to t with available capacity, we can push more flow through it! Forward edges: Residual capacity = c(u, v) - f(u, v) Backward edges: Can "undo" flow: capacity = f(u, v) Start with f(u, v) = 0 for all edges While there exists an augmenting path p from s to t: Find the bottleneck capacity along p Augment flow along p by the bottleneck Let's watch the algorithm work step by step on a simple network: When Ford-Fulkerson terminates, the set of vertices reachable from s in the residual network forms one side of a minimum cut!

This is the written version of the interactive lesson above. See the full Discrete Math course.