Network Flow Basics

Math for CS · Axiom Academy

Max-flow min-cut and the Ford-Fulkerson method A source s (where flow originates) A sink t (where flow is absorbed) Think of it as a network of pipes. Each pipe has a maximum capacity. Water flows from the source to the sink. The question: what is the maximum total flow that can be pushed from s to t ? Capacity constraint: for every edge Conservation: For every vertex : flow in = flow out The value of a flow |f| is the total flow leaving the source (equivalently, the total flow arriving at the sink). This is one of the most important theorems in combinatorial optimization, proved by Ford and Fulkerson in 1956. The Ford-Fulkerson method finds the maximum flow by repeatedly finding and augmenting along paths from s to t . Forward edge: (u,v) with residual capacity c(u,v) - f(u,v) (room to push more flow) Backward edge: (v,u) with residual capacity f(u,v) (flow we can "undo") Backward edges are the crucial insight. They allow the algorithm to correct suboptimal choices by rerouting flow. Start with zero flow: f(u,v) = 0 for all edges. Build the residual graph G_f . Find an augmenting path — any s - t path in G_f . Push flow along this path: the amount pushed is the minimum residual capacity along the path (the bottleneck). Update f and repeat from step 2. When no augmenting path exists, f is a maximum flow. Path : push 8 units (bottleneck at ) Path : push 5 units (bottleneck at ) Path : push 2 units (residual: has 2 left, has 3, has 2 left)

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