Network Flow and the Max-Flow Min-Cut Theorem
Flow pushes as much as possible from a source to a sink without exceeding any edge's capacity. Augmenting paths in a residual graph find the maximum, and the theorem says that maximum equals the cheapest set of edges whose removal disconnects the two.
What a learner can do afterwards
- Find a maximum flow by repeatedly augmenting along paths in the residual graph
- Identify the minimum cut and check its capacity equals the flow
- Model bipartite matching as a flow problem and read the matching off the answer
1 · Read
After cheapest routes, the next puzzle is how much can travel at once. A flow network pushes as much as possible from a source to a sink without exceeding any edge's capacity. You keep pushing along paths with leftover room until no such path remains.
Edges from the source hold 4 and 3, and edges into the sink hold 3 and 5. Pushing carefully moves 7 units in total. The cheapest edge set whose removal disconnects source from sink also costs 7. Maximum flow equals minimum cut, every time.
The residual graph is your working map: it shows remaining room forward and undo room backward. Each augmenting path adds its bottleneck amount. When no path is left, the flow is maximum and the reached nodes mark the minimum cut.
To match workers to jobs, build a flow network: source to each worker, edges for who can do what, each job to the sink, every capacity 1. Run the flow and read the matching off the used middle edges.
Augment along leftover room until none remains, and the flow you pushed equals the cheapest cut.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.