Cuts, labelling procedure and max-flow min-cut

Cuts, labelling procedure and max-flow min-cut Flashcards

Spec 3.1–3 · Edexcel 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.

12 cards

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

See all 12 cards
What is the capacity of a cut?
The sum of the capacities of the arcs directed from XX to YY (arcs from YY to XX are ignored).
What do the sets XX and YY of a cut contain?
XX contains the source S and YY contains the sink T.
What two rules must a feasible flow obey?
Flow on each arc is between 00 and its capacity, and flow in equals flow out at every vertex other than S and T.
What is the value of a flow?
The amount leaving the source, which equals the amount entering the sink.
In the labelling procedure, what does the arrow in the direction of the arc show?
The amount by which the flow can be increased (capacity minus flow).
What does the arrow in the opposite direction show?
The amount by which the flow could be reduced (the current flow).
What is a flow-augmenting route?
A route from S to T along which the flow can be increased.
By how much is the flow increased on a route?
By the smallest number on the route.
What happens on a backward arc of a route?
The flow in that arc is reduced by the amount.
State the max-flow min-cut theorem.
The value of a maximum flow equals the capacity of a minimum cut.
How do you prove a flow is maximum?
Find a cut whose capacity equals the flow value.
When does the labelling procedure stop?
When T cannot be labelled, so no further augmenting route exists.

Flashcards