Back to the on-screen lesson ·
Augment along a path, keep the right to cancel, and stop when no path is left.
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 forward and backward residual capacities of an arc, order the steps of one augmenting round, find a path's bottleneck, write the residual graph after an augmentation, say what backward residual capacity is for, and state what stopping with no augmenting path proves.
You can write a network as balance rows and you know its matrix is totally unimodular. Maximum flow is the linear program those rows describe, and this lesson is the method that exploits their structure.
A flow respects every capacity and balances at every node but the source and the sink. The residual graph records what may still be changed: forwards, the capacity left; backwards, the flow already carried, which may be cancelled. An augmenting path is a source-to-sink path in it, and its bottleneck is its smallest residual.
Start with nothing flowing. Build the residual graph: each arc contributes a forward capacity of what it has left and a backward capacity of what it is carrying. Find any path from the source to the sink in it, send the bottleneck amount along it, and repeat. When no path remains, stop.
The backward capacities are the whole idea. Without them the method is greedy: an early path can commit flow along a route that blocks a better arrangement, and nothing can recover. With them, a later path may cancel an earlier commitment, and the result is exact rather than merely good.
Stopping proves something. When no path remains, take the nodes still reachable from the source. Every arc leaving that set is saturated and every arc entering it is empty, so the flow across it equals its capacity. Since no flow exceeds any cut, this flow is maximum and that cut is minimum — which is the next lesson's theorem, arriving early and for free.
Whole numbers come out whole. Every bottleneck is a difference of whole numbers, so with whole capacities every flow the method holds is whole.
Another way: steps
Another way: example
Arcs $s \to a$ ($10$), $s \to b$ ($5$), $a \to b$ ($15$), $a \to t$ ($5$), $b \to t$ ($10$). Augment $s, a, t$ by $5$; $s, b, t$ by $5$; then $s, a, b, t$ by $5$. Total $15$, and no path remains.
The backward residual is read as flow travelling the wrong way down a one-way arc. It is not: it is permission to cancel. The other error is stopping when no path of unused arcs remains, which is the greedy method and can finish below the maximum.
Arcs $s \to a$ and $s \to b$ of capacity $1$, $a \to b$ of capacity $1$, and $a \to t$, $b \to t$ of capacity $1$.
A small awkward network.
Augment $s, a, b, t$ by $1$. Now $s \to a$, $a \to b$ and $b \to t$ are all full, and a greedy method stops at $1$.
An unlucky first path.
The residual graph still has $s \to b$, the backward arc $b \to a$, and $a \to t$. Augmenting along it reaches $2$, which is the maximum.
The undo recovers it.
Every unit uses all three arcs, so the amount is the smallest residual, $2$.
The bottleneck.
The middle arc saturates: its forward residual falls to zero, and the next path must avoid it.
Three arcs have capacities $5$, $12$ and $7$ and currently carry $3$, $3$ and $3$. Fill in each arc's residual capacity forwards and backwards.
| Capacity | Flow | Residual forwards | Residual backwards | |
|---|---|---|---|---|
| First arc | 5 | 3 | ||
| Second arc | 12 | 3 | ||
| Third arc | 7 | 3 |
A network with $6$ nodes is to be given a maximum flow. Put one round of the method into order.
Number the steps in order (write the number in the box):
An augmenting path uses three arcs whose residual capacities are $3$, $8$ and $12$. How much flow can this round send?
Answer:
An arc of capacity $10$ carries $3$. The residual graph gives it a backward capacity of $3$. What is that for?
A network on nodes $1$, $2$, $3$ has arcs $1 \to 2$ of capacity $9$, $2 \to 3$ of capacity $4$ and $1 \to 3$ of capacity $5$, and nothing is flowing yet. Augment along $1 \to 2 \to 3$ and write the residual capacity matrix, rows the node an arc leaves.
This task has no paper form; do it on a device.
The method has stopped: no augmenting path remains. Select everything that follows.
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.
Three arcs have capacities $6$, $12$ and $6$ and currently carry $3$, $3$ and $3$. Fill in each arc's residual capacity forwards and backwards.
| Capacity | Flow | Residual forwards | Residual backwards | |
|---|---|---|---|---|
| First arc | 6 | 3 | ||
| Second arc | 12 | 3 | ||
| Third arc | 6 | 3 |
You can augment a flow along a path and build the residual graph it leaves. Say in your own words why a method without backward residuals can stop below the maximum.
7. Your turn: an augmenting path's residual capacities are $6$, $2$ and $9$. How much is sent, and which arc saturates?, step 2