Lesson 178
Network Flow
Max Flow · Ford–Fulkerson · Min Cut
1:00How to maximize flow through a capacity-constrained directed network using Ford-Fulkerson augmenting paths, the residual graph, and the max-flow min-cut theorem.
By the end, you can
- Define the capacity constraint and conservation rule, and verify whether a given flow is valid.
- Identify the source, sink, augmenting paths, and bottleneck in a concrete flow network.
- Trace the Ford-Fulkerson algorithm step by step, updating flows and residual edges.
- Explain why residual backward edges are essential for correctness, not just a bookkeeping trick.
- Compute the max flow of a small network by hand and confirm it matches the minimum cut.
- Define an S-T cut, compute its capacity, and identify the minimum cut in a small network.
- State the max-flow min-cut theorem and explain what it implies about the termination of Ford-Fulkerson.
- Compare the time complexity of Ford-Fulkerson O(E·maxflow) and Edmonds-Karp O(V·E²).
- Describe how bipartite matching, image segmentation, and network routing reduce to max-flow.
Up next in Algorithms & Graph Algorithms
