Back to the on-screen lesson ·
A cut bounds every flow; duality and total unimodularity make the best bound exact.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute the capacity of a cut by adding only its forward crossings, find the maximum flow from the smallest cut, bracket a maximum flow between a flow and a cut you hold, and give the argument that max-flow min-cut is linear programming duality together with total unimodularity.
You can augment a flow until no path remains, and you have met weak and strong duality in unit 4. This lesson puts the two together: the thing the flow method stops at is a dual solution, and that is why it is a proof.
A cut is a split of the nodes into a source side holding $s$ and a sink side holding $t$. Its capacity adds the capacities of the arcs crossing it forwards — from the source side to the sink side. Arcs inside either side, and arcs running back, contribute nothing.
A cut bounds a flow. Everything reaching the sink must cross from the source side to the sink side at some point, so the flow value is at most the total forward capacity across any cut. That is weak duality, proved by counting rather than algebra — and it is why backward arcs do not count: they reduce the net crossing rather than allowing more.
Max-flow min-cut says the best bound is attained: the maximum flow equals the smallest cut capacity. Two facts give it. Maximum flow is a linear program, so strong duality hands its dual an equal optimum; and the dual's matrix is a network matrix, so total unimodularity puts that optimum at an integral vertex — a vector of zeros and ones, which is a set of arcs, which is a cut.
Without the first the two values could differ. Without the second the dual optimum might be a fractional blend that no cut achieves, and the theorem would be an inequality. So this is not a separate discovery about graphs: it is the duality of unit 4 plus one structural property, and the same pair gives König's theorem and Hall's.
The general integer case has neither. Its bound and its answer genuinely differ, and that gap is what unit 5 spends its time closing.
Another way: steps
Another way: picture
Draw a loop around the source and some of the nodes. Every arc the loop cuts on its way out counts; every arc it cuts on the way in does not; every arc wholly inside or wholly outside is untouched. The total of the outward ones is the cut's capacity.
Backward arcs are added into a cut's capacity, which inflates it and can make the minimum cut look larger than the maximum flow. The other error is taking any set of saturated arcs for a minimum cut: the arcs have to separate $s$ from $t$, and the ones the residual reachability set produces are the ones that do.
The augmenting method has stopped. From $s$, the residual graph still reaches $a$ and no further.
The reachable set.
So the cut is $\{s, a\}$ against the rest. Every arc leaving it is saturated, or its far end would have been reachable.
Saturated by construction.
Its capacity therefore equals the flow, so the flow is maximum and the cut is minimum. Both facts, from one search.
The certificate.
Only the arcs running from the source side to the sink side count.
Backward arcs are ignored.
So the capacity is $8 + 8 = 16$, and the two backward arcs add nothing.
A network has arcs $s \to a$ of capacity $2$, $s \to b$ of $4$, $a \to b$ of $8$, $a \to t$ of $5$ and $b \to t$ of $4$. Fill in the capacity of each cut.
| Capacity | |
|---|---|
| Source side $\{s\}$ | |
| Source side $\{s, a\}$ | |
| Source side $\{s, b\}$ | |
| Source side $\{s, a, b\}$ |
A network's cuts have capacities $17$, $24$ and $31$, and no cut is smaller than $17$. What is the maximum flow?
Answer:
The source side of a cut is $\{s, a\}$ and the sink side is $\{b, t\}$. Select every arc whose capacity counts towards this cut.
This task has no paper form; do it on a device.
Is this right: every cut of a network bounds every feasible flow?
You have found a flow worth $8$ and a cut of capacity $14$. Give the interval the maximum flow must lie in.
This task has no paper form; do it on a device.
Build the argument that the maximum flow in a network of $5$ nodes equals the capacity of its minimum cut.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A network has arcs $s \to a$ of capacity $6$, $s \to b$ of $4$, $a \to b$ of $2$, $a \to t$ of $9$ and $b \to t$ of $2$. Fill in the capacity of each cut.
| Capacity | |
|---|---|
| Source side $\{s\}$ | |
| Source side $\{s, a\}$ | |
| Source side $\{s, b\}$ | |
| Source side $\{s, a, b\}$ |
You can compute cut capacities, use them to bound a flow, and say where max-flow min-cut comes from. Say in your own words why an arc running back across a cut adds nothing to its capacity.
7. Your turn: a cut has forward arcs of capacity $8$ and $8$ and two backward arcs of capacity $9$ each. What is its capacity?, step 2