What is the increase along an augmenting route?

The smallest spare capacity (or backward amount) on the route.

How can a backward arc be used?

Travel against the arc's direction to cancel some of its flow, up to the flow currently on it.

When does the augmenting algorithm stop?

When no flow-augmenting route from source to sink exists.

How do you prove the final flow is maximal?

Find the cut whose arcs are all saturated, show its capacity equals the flow, and quote the max-flow min-cut theorem.

What does an arc with limits [l,u] mean?

The flow on the arc must be at least l and at most u.

What is the capacity of a cut when arcs have lower capacities?

Sum of upper capacities of arcs from X to Y, minus sum of lower capacities of arcs from Y to X.

How do you model a node with restricted capacity?

Split it into two nodes joined by an arc with the restricted capacity; arcs in go to the first, arcs out leave the second.

When does raising an arc's capacity raise the maximum flow?

Only if the arc is in every minimum cut, and by no more than the next smallest cut allows.

Augmenting flows and refinementsAQA A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is a flow-augmenting route?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What is a flow-augmenting route?: A route from source to sink along which the flow can be increased, using forward spare capacity and backward flow.
How do you find the spare capacity of an arc?: Capacity minus current flow.
What is the increase along an augmenting route?: The smallest spare capacity (or backward amount) on the route.
How can a backward arc be used?: Travel against the arc's direction to cancel some of its flow, up to the flow currently on it.
When does the augmenting algorithm stop?: When no flow-augmenting route from source to sink exists.
How do you prove the final flow is maximal?: Find the cut whose arcs are all saturated, show its capacity equals the flow, and quote the max-flow min-cut theorem.
What does an arc with limits $[l,u]$ mean?: The flow on the arc must be at least $l$ and at most $u$ .
What is the forward spare capacity on an arc with limits $[l,u]$ carrying $f$ ?: $u-f$ .
How much flow can be cancelled backwards on that arc?: $f-l$ .
What is the capacity of a cut when arcs have lower capacities?: Sum of upper capacities of arcs from $X$ to $Y$ , minus sum of lower capacities of arcs from $Y$ to $X$ .
How do you model a node with restricted capacity?: Split it into two nodes joined by an arc with the restricted capacity; arcs in go to the first, arcs out leave the second.
Where do you find the bottleneck in a network?: In the arcs of a minimum cut.
When does raising an arc's capacity raise the maximum flow?: Only if the arc is in every minimum cut, and by no more than the next smallest cut allows.

Exam questions on Augmenting flows and refinements

A network has source $S$ , sink $T$ and nodes $A$ and $B$ . The directed arcs and their capacities are $SA$ 6, $SB$ 3, $AB$ 5, $AT$ 3 and $BT$ 4. An initial flow of 4 units is sent along the route $S\to A\to B\to T$ .
Show how the flow of 6 can be increased further, and prove that the resulting flow is a maximum.2 marks
Water flows from a source $S$ to a sink $T$ through junctions $A$ and $B$ . Each pipe has a lower and an upper limit on its flow, in litres per second, written $[\text{lower},\text{upper}]$ : $SA$ $[3,8]$ , $SB$ $[2,5]$ , $AB$ $[1,4]$ , $AT$ $[4,7]$ and $BT$ $[3,6]$ . Water flows in the direction of each arc.
Show that the value of every feasible flow is at least 7 litres per second.2 marks
A sorting centre network has source $S$ , sink $T$ and nodes $A$ , $B$ and $C$ . The directed arcs and their capacities (parcels per hour, in thousands) are $SA$ 8, $SB$ 7, $AB$ 4, $AC$ 5, $BC$ 6, $BT$ 5 and $CT$ 9. Node $B$ can handle at most 6 thousand parcels per hour in total.
Explain how the network can be modified to include the restriction on node $B$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).