Flows, cuts and the max-flow min-cut theorem

Flows, cuts and the max-flow min-cut theorem Flashcards

Spec DC1–DC3 · 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 network?
A network of directed arcs with capacities, a source where flow enters and a sink where it leaves.
State the two rules for a feasible flow.
Flow on each arc is at most its capacity (and non-negative), and flow in equals flow out at every intermediate node.
What is the value of a flow?
The total flow leaving the source, which equals the total flow arriving at the sink.
What does it mean for an arc to be saturated?
Its flow equals its capacity.
What is a cut?
A division of the nodes into two sets, one containing the source and one containing the sink.
How is the capacity of a cut found?
Add the capacities of the arcs directed from the source side to the sink side.
Are arcs directed from the sink side to the source side counted in a cut?
No. Only arcs leaving the source set are counted.
Compare any flow with any cut.
The value of any flow is at most the capacity of any cut.
State the max-flow min-cut theorem.
In any network the value of the maximum flow equals the capacity of the minimum cut.
How do you prove a flow is maximal?
Find a cut whose capacity equals the flow value, then quote the max-flow min-cut theorem.
When does raising an arc's capacity increase the maximum flow?
Only if the arc lies in every minimum cut.
What is a supersource and how is it joined?
A single added source, with an arc from it to each real source; each arc has the capacity of the supply.
What is a supersink and how is it joined?
A single added sink, with an arc into it from each real sink; each arc has the capacity of the demand.

Flashcards