What capacity goes on each arc from the super source?

The supply of the source it joins.

What capacity goes on each arc to the super sink?

The demand of the sink it comes from.

How do you model a vertex C with restricted capacity k?

Split it into C{in} and C{out} joined by an arc of capacity k.

Where do arcs go when a vertex is split?

Arcs into C end at C{in}; arcs out of C start at C{out}.

What does [3, 8] on an arc mean?

The flow must be at least 3 and at most 8.

Capacity of a cut with lower capacities?

Sum of upper capacities from X to Y minus sum of lower capacities from Y to X.

When is a flow feasible?

When every arc has lower \le flow \le upper and flow in = flow out at each intermediate vertex.

Why might the maximum flow stop rising after an improvement?

Another cut becomes the smallest cut.

Multiple sources and sinks, restricted capacities and optimal flowEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is a super source?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What is a super source?: An added vertex joined to every source, so that the network has one source.
What capacity goes on each arc from the super source?: The supply of the source it joins.
What capacity goes on each arc to the super sink?: The demand of the sink it comes from.
How do you model a vertex $C$ with restricted capacity $k$ ?: Split it into $C_{\text{in}}$ and $C_{\text{out}}$ joined by an arc of capacity $k$ .
Where do arcs go when a vertex is split?: Arcs into $C$ end at $C_{\text{in}}$ ; arcs out of $C$ start at $C_{\text{out}}$ .
What does $[3, 8]$ on an arc mean?: The flow must be at least $3$ and at most $8$ .
Forward label on an arc with lower and upper capacities?: Upper capacity minus flow.
Backward label on an arc with lower and upper capacities?: Flow minus lower capacity.
Capacity of a cut with lower capacities?: Sum of upper capacities from $X$ to $Y$ minus sum of lower capacities from $Y$ to $X$ .
When is a flow feasible?: When every arc has lower $\le$ flow $\le$ upper and flow in = flow out at each intermediate vertex.
Which arcs should you change to increase the maximum flow?: Those in the minimum cut.
Why might the maximum flow stop rising after an improvement?: Another cut becomes the smallest cut.

Exam questions on Multiple sources and sinks, restricted capacities and optimal flow

Two depots, P and Q, supply goods to two shops, U and V, through junctions A and B. Depot P can supply at most 9 units and depot Q at most 6 units. Shop U can receive at most 7 units and shop V at most 8 units. The directed roads and their capacities, in units, are: PA 6, PB 4, QB 5, AU 4, AV 3, BU 2 and BV 6. To find the greatest total delivery, a super source S and a super sink T are added.
A flow of value $14$ is found in which depot P supplies $9$ units. Show that this flow is a maximum flow, and find how much of the supply at depot Q is not used.2 marks
A pipeline network has source S, sink T and junctions A, B, C and D. The directed pipes and their capacities, in units per hour, are: SA 8, SB 7, AC 6, AT 3, BC 5, CT 6, CD 4 and DT 5. Junction C can handle at most 7 units per hour in total.
The restriction at junction C is removed. Find the new maximum flow and justify your answer.2 marks
A network has source S, sink T and vertices A, B and C. Each arc has a lower and an upper capacity, written [lower, upper]: SA [3, 9], SB [2, 6], AB [1, 4], AC [0, 5], BC [2, 6], BT [0, 4] and CT [4, 10].
Find the capacity of the cut with $X=\{S,B\}$ and $Y=\{A,C,T\}$ , and of the cut with $X=\{S,A,B,C\}$ and $Y=\{T\}$ . What can you deduce 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).