What do the sets X and Y of a cut contain?

X contains the source S and Y contains the sink T.

What two rules must a feasible flow obey?

Flow on each arc is between 0 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.

Cuts, labelling procedure and max-flow min-cutEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is the capacity of a cut?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What is the capacity of a cut?: The sum of the capacities of the arcs directed from $X$ to $Y$ (arcs from $Y$ to $X$ are ignored).
What do the sets $X$ and $Y$ of a cut contain?: $X$ contains the source S and $Y$ contains the sink T.
What two rules must a feasible flow obey?: Flow on each arc is between $0$ 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.

Exam questions on Cuts, labelling procedure and max-flow min-cut

A network has source S, sink T and intermediate vertices A and B. The directed arcs and their capacities are: SA 7, SB 5, AB 3, AT 4 and BT 6 (for example, arc SA goes from S to A and has capacity 7).
A flow of value $10$ is found: SA 7, SB 3, AB 3, AT 4 and BT 6. Use a cut to prove that this flow is a maximum flow.2 marks
A network has source S, sink T and intermediate vertices A, B and C. The directed arcs and their capacities are: SA 9, SB 7, AB 4, AC 5, BC 6, BT 4 and CT 8. A flow is already in the network: SA 5, SB 3, AB 2, AC 3, BC 3, BT 2 and CT 6, so the flow value is 8.
Find the amount by which the flow can be increased along the route S, A, C, T, and state the new flow value.2 marks
A network has source S, sink T and intermediate vertices A, B, C and D. The directed arcs and their capacities are: SA 10, SB 8, AC 7, BA 3, BD 6, CT 9, DC 4 and DT 5.
Find the capacity of the cut that separates $\{S,A,C\}$ from $\{B,D,T\}$ , and of the cut that separates $\{S,A,B\}$ from $\{C,D,T\}$ . What do these tell you about the maximum flow?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).