Augmenting flows and refinements

Augmenting flows and refinements Flashcards

Spec DC4–DC7 · AQA A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

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][l,u] mean?
The flow on the arc must be at least ll and at most uu.
What is the forward spare capacity on an arc with limits [l,u][l,u] carrying ff?
u−fu-f.
How much flow can be cancelled backwards on that arc?
f−lf-l.
What is the capacity of a cut when arcs have lower capacities?
Sum of upper capacities of arcs from XX to YY, minus sum of lower capacities of arcs from YY to XX.
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.

Flashcards