Maximum Flow & Minimum Cut

How to read this

• Each edge shows flow/capacity (x/u). Flow must stay between 0 and u, and at every middle vertex flow in = flow out.
• A labeled vertex j carries (l, i+) or (l, i−): l = how much extra flow can reach j; i = the vertex it was reached from; + means along a forward edge with room left, − means against an edge that already carries flow.
• Chips under the graph are the queue; ↑ marks vertices already dequeued (as in Levitin's figures).
• When the sink is labeled, its first label is the augmentation amount. Follow second labels backward to trace the path, add on forward edges, subtract on backward ones.
• When the sink stays unlabeled, the labeled set X (green) and the rest form the minimum cut (red dashed edges).

Try this

1. Levitin §10.2 example: predict the second augmenting path. It must use edge 2→3 backward: 1→4→3←2→5→6 — the only way to use the idle capacity on 1→4.
2. At the end, check the cut {(1,2), (4,3)}: capacity 2 + 1 = 3 = the flow value. Try any other cut by hand (e.g. X = {1}: 2 + 3 = 5) — it's never smaller.
3. Pick the bad-path example, U = 20, with "Unlucky" path choice: 40 augmentations of 1 unit each. Switch to BFS: just 2. Now drag U to 40 — the unlucky count doubles, BFS stays at 2.
4. Raise capacity 4→3 from 1 to 2 in the Levitin §10.2 example. Does the max flow grow? (Yes, to 4 — and now two cuts tie at capacity 4: X = {1, 4} and X = {1, 3, 4}.)
5. Lesson network: the third augmenting path s→c→b←a→d→t reroutes 3 units from b over to d. Predict the final cut before playing to the end.