Multiple sources and sinks, restricted capacities and optimal flow

Multiple sources and sinks, restricted capacities and optimal flow Test

Spec 3.4–5 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Multiple sources and sinks, restricted capacities and optimal flow

Total 27 marks

Name

Class

Date

  1. 1
    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)
    Which arcs and capacities should join the super source S to the depots?
    [1 mark]
    • ASP with capacity 9 and SQ with capacity 6
    • BSP with capacity 6 and SQ with capacity 9
    • CSP with capacity 7 and SQ with capacity 8
    • DSP and SQ, each with infinite capacity
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    What is the capacity of the cut that separates {S,P,Q,A}\{S,P,Q,A\} from {B,U,V,T}\{B,U,V,T\}?
    [1 mark]
    • A2222
    • B1616
    • C1111
    • D77
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    A flow of value 1414 is found in which depot P supplies 99 units. Show that this flow is a maximum flow, and find how much of the supply at depot Q is not used.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: cut separating {S,Q}\{S,Q\} from the other vertices: arcs SP and QB, capacity 9+5=149+5=14, equal to the flow, so the flow is maximum
    B1: Q supplies
    14−9=514-9=5 units, so 6−5=16-5=1 unit of Q's supply is unused
    Accept: any correct cut of capacity
    1414

    Total for question 1: 4 marks

  2. 2
    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.
    (a)
    Which of these correctly models the restriction at junction C?
    [1 mark]
    • AReduce the capacity of arc CT to 7
    • BDelete junction C and all its arcs
    • CReplace C by two vertices, CinC_{\text{in}} and CoutC_{\text{out}}, with arcs into C ending at CinC_{\text{in}}, arcs out of C starting at CoutC_{\text{out}}, and an arc CinCoutC_{\text{in}}C_{\text{out}} of capacity 7
    • DAdd a super sink with capacity 7
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    What is the maximum flow through the network, in units per hour?
    [1 mark]
    • A1313
    • B1515
    • C77
    • D1010
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    The restriction at junction C is removed. Find the new maximum flow and justify your answer.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: cut separating {S,B}\{S,B\} from the other vertices has capacity SA ++ BC =8+5=13=8+5=13, so the maximum flow is at most 1313
    B1: a flow of
    1313 exists, for example SA 8, SB 5, AT 3, AC 5, BC 5, CT 6, CD 4, DT 4, so the maximum flow is 1313
    Accept: any valid flow of value
    1313

    Total for question 2: 4 marks

  3. 3
    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].
    (a)
    Find the capacity of the cut with X={S,B}X=\{S,B\} and Y={A,C,T}Y=\{A,C,T\}, and of the cut with X={S,A,B,C}X=\{S,A,B,C\} and Y={T}Y=\{T\}. What can you deduce about the maximum flow?
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: first cut: upper capacities SA, BC and BT, 9+6+4=199+6+4=19, minus the lower capacity of AB, which is directed from YY to XX: 19−1=1819-1=18
    B1: second cut: BT and CT,
    4+10=144+10=14
    B1: the maximum flow is at most
    1414
    Do not accept:
    1919 for the first cut
    (b)
    A feasible flow is SA 5, SB 4, AB 1, AC 4, BC 3, BT 2 and CT 7, with value 99. In the labelling procedure, state the two labels on arc AB and explain the second. Then find a flow-augmenting route that uses arc SB, and the new flow value.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: arc AB labels: 33 in its own direction (4−14-1) and 00 in the opposite direction (1−11-1)
    R1: the flow cannot be reduced because it is already at the lower capacity of
    11
    M1: route S, B, T with spare capacities SB
    6−4=26-4=2 and BT 4−2=24-2=2
    A1: flow increases by
    22, so the new flow value is 1111
    Accept: the route S, B, C, T if the amounts are correct and give the same new flow

    Total for question 3: 7 marks

  4. 4
    A network of pipes has source S, sink T and junctions A, B and C. Each pipe has a minimum and a maximum flow, written [minimum, maximum], in units per minute: SA [1, 11], SB [0, 10], AB [3, 9], AC [1, 9], AT [3, 7], BT [2, 8] and CT [0, 5]. A feasible flow of value 12 has SA 8, SB 4, AB 4, AC 1, AT 3, BT 8 and CT 1.
    (a)
    Use the labelling procedure to find the maximum flow, stating each flow-augmenting route and the amount by which the flow increases. Show how the label on the backward arc is found.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: a valid first route using forward spare capacity, for example S, A, T
    A1: correct amount, for example
    33 (spare capacities SA 33, AT 44), giving flow value 1515
    M1: a route using arc AB backwards, for example S, B, A, T

    B1: backward label on AB is flow minus lower capacity,
    4−3=14-3=1
    A1: the route increases the flow by
    11 (other labels at least 11)
    A1: maximum flow
    1616
    Accept: any valid order of routes that uses the backward arc and finishes with flow
    1616
    (b)
    (i) Prove that the flow in (a) is a maximum. (ii) The operator can either reduce the minimum flow in AB from 33 to 11, or raise the maximum flow in CT from 55 to 99. Evaluate which is worth doing.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) cut with X={S,B}X=\{S,B\} and Y={A,C,T}Y=\{A,C,T\}: upper capacities SA ++ BT =11+8=19=11+8=19
    A1: subtract the lower capacity of AB (directed from
    YY to XX): 19−3=1619-3=16, equal to the flow, so the flow is maximum
    M1: (ii) reducing the minimum in AB to
    11 raises this cut to 19−1=1819-1=18
    A1: the next smallest cuts have capacity
    2020 or more (for example {S,A,B,C}\{S,A,B,C\} has 7+8+5=207+8+5=20), so the maximum flow rises to 1818
    B1: CT is not in this cut, so raising its maximum leaves the minimum cut, and the maximum flow, at
    1616
    R1: reducing the minimum in AB is worthwhile (flow up by
    22); raising CT gives no benefit

    Total for question 4: 12 marks

End of questions

Subtopic tests