Advanced · Module 19 · Lesson 9
Network flow
Residual graphs, augmenting paths, and min-cut duality.
15–25 min readLesson 123 of 123
Lesson 123 of 123
1d streakTheory lesson · Step-by-step
Understand Network flow
Residual graphs, augmenting paths, and min-cut duality.
Worked approach
Trace the reasoning step by step
- 1Build forward and reverse residual edges.
- 2Find an augmenting path.
- 3Send its bottleneck flow.
- 4Update both residual directions until no path remains.
Concrete example
Send flow through s→a capacity 3 and a→t capacity 2.
- 1Augment 2 along s,a,t.
- 2Decrease forward residual capacities.
- 3Increase reverse residual capacities.
Flow is 2 and the residual graph records how it can be revised.
What must remain true (Loop Invariant)
The residual graph records how much flow can still be sent or undone on every edge.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Graph processing
Algorithm-dependent
O(V + E)
Assumes adjacency-list representation unless stated otherwise.When to use it
- Large constraints requiring specialized string, range, geometry, or network tools.
- Repeated queries or updates that justify preprocessing.
- Problems with a strong algebraic, heuristic, or residual invariant.
Common mistakes
- Using a specialized structure without checking its operation assumptions.
- Mixing zero-based and one-based indexes.
- Memorizing formulas without proving what each stored value means.
Practice prompts
- Reproduce the worked Network flow example without looking at the trace.
- Change one input condition and explain whether the Network flow invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.