Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Flow & Matching  ›  Lesson

Min Cut & Duality

Min Cut & Duality 30 minThe nodes still reachable from source in the final residual graph, and the pipes crossing out of them, sum to exactly the max flow
You're building a piece ofMeridian — the dispatcher
This piece — limiting_cut(): Names the exact pipes that are choking the network and proves no more can get through them.
Scenario Dispatch doesn't just want the number — they want to know WHICH pipes are actually choking the network, so maintenance knows what's worth widening and what isn't.
Your task
Build limiting_cut(pipes, source, sink). Run max flow, then find every node still reachable from source in the final residual graph (edges with capacity left, forward or backward). Return {"max_flow": total, "source_side": sorted reachable nodes, "cut_edges": sorted [from, to] pipes leaving that set, "cut_capacity": their capacity sum}. Example: limiting_cut([["s", "a", 3], ["a", "t", 2]], "s", "t") -> {"max_flow": 2, "source_side": ["a", "s"], "cut_edges": [["a", "t"]], "cut_capacity": 2}.

Min Cut & Duality

In short: Once max flow stops growing, ask one question: which nodes can still be reached from the source using leftover residual capacity? That set is the source side of a cut, and the original pipes leaving it — the crossing edges — are exactly the ones running at full capacity. Their capacities always sum to the max flow. This is max-flow min-cut duality: the biggest amount you can push and the smallest set of pipes you'd have to sever to stop everything are the same number, proven by one reachability check on the graph the last lesson already built.

A network split by a dashed vertical line: depot, dock, mill, axle and berth shaded green on the left as reachable, harbour alone in white on the right, with two red pipes (axle-harbour at 4, berth-harbour at 1) crossing the line and a note that 4 plus 1 equals the exact max flow

The reachable set, after the fact

The last lesson's Edmonds-Karp run on Meridian's depot network stopped because BFS couldn't reach harbour any more. Look at why, in the final residual graph: every pipe still carrying forward residual capacity, plus every reverse edge flow has opened.

watch it move · graph

The residual graph after max flow stops growing. A dashed line through the numbers would show it, but the real test is simpler — just walk from depot using whatever still has capacity.

Start at depot, the source, and walk only edges with capacity left — forward pipes that aren't full, and reverse edges flow has opened. 6 nodes, 14 edges, directed. At depot.

1 / 6

Why this always works

Call the reachable set S. Every pipe leaving S must be full — if it had residual capacity left, its far end would be reachable too, and it wouldn't be outside S. So the flow crossing S is at least the sum of those pipes' capacities. It can't be more, because conservation means everything that crosses S has to cross it somewhere. Those two facts pin the flow crossing S to exactly the sum of the crossing capacities — and since this is the actual max flow (BFS just confirmed no more fits), S's crossing capacity is the minimum possible over every way to split the network into a source side and a sink side. Max flow equals min cut, always, not just in this example.

In code

python

Nothing here is a new algorithm. It's the same residual graph, read a second time with a different question: not "can I still push more?" but "who can depot still reach?"

Quick practice

A cut that isn't the minimum

Any split of the nodes into a source side and a sink side is a cut, and its crossing capacity is always at least the max flow — min-cut just says the reachable split is the smallest one:

What does this print?
# the diamond network: s-a(3), s-b(2), a-b(2), a-t(2), b-t(3)
minimum_cut = 3 + 2          # {s} vs everything else
a_bigger_cut = 2 + 2 + 2     # {s, a} vs {b, t}: a-b, a-t and s-b all cross
print(minimum_cut, a_bigger_cut)

Picking the wrong side

broken — fix it

crossing_edges should return every pipe whose `from` end is inside source_side and whose `to` end is outside it. Fix the condition so it checks a in side and b not in side.

What this buys Meridian

A max-flow number alone tells dispatch "5 units an hour, full stop." The cut tells them why: axle-harbour and berth-harbour, together, are the entire bottleneck. Every other pipe in the network has slack. Widening anything that isn't on the cut buys nothing — the next lesson's dispatcher exercise leans on exactly that fact to decide where Meridian's maintenance budget should go.

What it answers
max flow How much, total
min cut Which pipes, exactly, are the reason it isn't more

❓ Cross-question: "Is the min cut always unique?" No. Two different-looking cuts can both equal the max flow, if there are two genuinely separate bottlenecks of the same size. The reachable-set method always finds one valid minimum cut, not necessarily the only one.

🎯 Your turn

Write limiting_cut(pipes, source, sink). Run max flow, then find every node still reachable from source in the final residual graph. Return {"max_flow": total, "source_side": sorted reachable nodes, "cut_edges": sorted [from, to] pipes leaving that set, "cut_capacity": their capacity sum}:

  • limiting_cut([["s", "a", 3], ["a", "t", 2]], "s", "t") → {"max_flow": 2, "source_side": ["a", "s"], "cut_edges": [["a", "t"]], "cut_capacity": 2}

Hint: reuse the max-flow loop, keep the residual graph afterwards, then walk from source over whatever still has capacity left.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian's dispatcher is built. ✅

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upWhich pipes cross the line

Write crossing_edges(pipes, source_side) where source_side is a list of nodes. Return the sorted list of [from, to] pairs for every pipe whose from is in source_side and whose to isn't. Example: crossing_edges([["s", "a", 3], ["s", "b", 2]], ["s"]) -> [["s", "a"], ["s", "b"]].

min-cutnetwork-flow
DrillHow big is this cut

Write cut_capacity(pipes, source_side) returning the total capacity of every pipe crossing out of source_side (same rule as crossing_edges). Example: cut_capacity([["s", "a", 3], ["s", "b", 2]], ["s"]) -> 5.

min-cutnetwork-flow
BuildWho's still reachable after the flow is maxed

Write reachable_in_residual(residual, source) where residual is a dict of dicts (residual[a][b] is the residual capacity from a to b). Return the sorted list of every node reachable from source using only edges with residual capacity greater than 0 — this is the source side of the min cut. Example: reachable_in_residual({"s": {"a": 2}, "a": {"s": 0}}, "s") -> ["a", "s"].

residual-graphmin-cut
BossCheapest pipes to widen first

Write widen_candidates(pipes, source_side) returning the cut's crossing pipes as a list of [from, to], sorted by capacity ascending (narrowest first, alphabetical on a tie) — the order Meridian should consider widening them in, since the narrowest crossing pipe is the cheapest place to add a unit of extra capacity. Example: widen_candidates([["s", "a", 3], ["s", "b", 2]], ["s"]) -> [["s", "b"], ["s", "a"]].

min-cutmax-flow
CapstoneWould widening this one pipe actually help?

Write widen_helps(pipes, source, sink, edge) where edge is a [from, to] pair that appears in pipes. Add 1 to that one pipe's capacity, recompute the max flow, and return True if the max flow increased, False if it stayed the same. Example: widen_helps([["s", "a", 3], ["a", "t", 2]], "s", "t", ["a", "t"]) -> True.

max-flowmin-cutnetwork-flow
limiting_cut.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
limiting_cut(pipes, source, sink) → dictThe max flow, the source-reachable set after it, the pipes crossing out of it, and their capacity.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.