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.

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.

Flows, cuts and the max-flow min-cut theoremAQA A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is a flow network?

Tap or press Space to reveal

Tap card or press Space to flip

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.

Exam questions on Flows, cuts and the max-flow min-cut theorem

A network has source $S$ , sink $T$ and intermediate nodes $A$ and $B$ . The directed arcs and their capacities are $SA$ 7, $SB$ 6, $AB$ 2, $AT$ 4 and $BT$ 8.
Explain why the flow from $S$ to $T$ cannot exceed 12.2 marks
Two factories $F_1$ and $F_2$ can make at most 10 and 8 tonnes of a product per hour. They send it through a depot $D$ to two shops $T_1$ and $T_2$ , which can receive at most 8 and 6 tonnes per hour. The directed arcs and their capacities (tonnes per hour) are $F_1D$ 9, $F_2D$ 6, $F_1T_1$ 3, $DT_1$ 5 and $DT_2$ 7.
Explain why arc $DT_2$ cannot be saturated in a maximum flow.2 marks
A network has source $S$ , sink $T$ and nodes $A$ , $B$ and $C$ . The directed arcs and their capacities are $SA$ 10, $SB$ 6, $AB$ 3, $AC$ 5, $BC$ 4, $BT$ 2 and $CT$ 9.
Find the capacity of the cut that separates $\{S,B\}$ from $\{A,C,T\}$ .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).