Augmenting flows and refinements

Augmenting flows and refinements Test

Spec DC4–DC7 · AQA 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

AQA A-Level Further Maths

Augmenting flows and refinements

Total 27 marks

Name

Class

Date

  1. 1
    A network has source SS, sink TT and nodes AA and BB. The directed arcs and their capacities are SASA 6, SBSB 3, ABAB 5, ATAT 3 and BTBT 4. An initial flow of 4 units is sent along the route S→A→B→TS\to A\to B\to T.
    (a)
    By how much can the flow be increased along the route S→A→TS\to A\to T?
    [1 mark]
    • A33
    • B66
    • C22
    • D44
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    The flow is increased to 6 by sending 2 more units along S→A→TS\to A\to T. Which route is now a flow-augmenting route?
    [1 mark]
    • AS→B→A→TS\to B\to A\to T
    • BS→B→TS\to B\to T
    • CS→A→B→TS\to A\to B\to T
    • DS→A→TS\to A\to T
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Show how the flow of 6 can be increased further, and prove that the resulting flow is a maximum.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: augmenting route S→B→A→TS\to B\to A\to T with ABAB used backwards, increasing the flow by 1 to 7
    R1: the cut
    {S,A,B}∣{T}\{S,A,B\}|\{T\} has capacity 3+4=73+4=7, so by the max-flow min-cut theorem 7 is maximal
    Accept: any correct statement that
    ATAT and BTBT are both saturated

    Total for question 1: 4 marks

  2. 2
    Water flows from a source SS to a sink TT through junctions AA and BB. Each pipe has a lower and an upper limit on its flow, in litres per second, written [lower,upper][\text{lower},\text{upper}]: SASA [3,8][3,8], SBSB [2,5][2,5], ABAB [1,4][1,4], ATAT [4,7][4,7] and BTBT [3,6][3,6]. Water flows in the direction of each arc.
    (a)
    Flows are given in the order SA,SB,AB,AT,BTSA,SB,AB,AT,BT. Which of these is a feasible flow?
    [1 mark]
    • A(5,2,0,5,2)(5,2,0,5,2)
    • B(7,3,2,4,5)(7,3,2,4,5)
    • C(9,4,2,7,6)(9,4,2,7,6)
    • D(6,4,2,4,6)(6,4,2,4,6)
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    What is the maximum value of a feasible flow, in litres per second?
    [1 mark]
    • A1616
    • B1313
    • C77
    • D1111
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Show that the value of every feasible flow is at least 7 litres per second.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: the value of the flow equals the flow into TT, which is AT+BTAT+BT
    A1:
    AT≥4AT\geq4 and BT≥3BT\geq3, so the value is at least 4+3=74+3=7
    AG

    Total for question 2: 4 marks

  3. 3
    A sorting centre network has source SS, sink TT and nodes AA, BB and CC. The directed arcs and their capacities (parcels per hour, in thousands) are SASA 8, SBSB 7, ABAB 4, ACAC 5, BCBC 6, BTBT 5 and CTCT 9. Node BB can handle at most 6 thousand parcels per hour in total.
    (a)
    Explain how the network can be modified to include the restriction on node BB.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: replace BB by two nodes B1B_1 and B2B_2
    B1: arcs
    SBSB and ABAB go into B1B_1; arcs BCBC and BTBT leave from B2B_2
    B1: add an arc
    B1B2B_1B_2 with capacity 6
    (b)
    A flow of value 11 is found in the modified network. Without the restriction the maximum flow is 14. Prove that 11 is the maximum flow in the modified network and state the effect of the restriction.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: a cut separating SS from TT, e.g. {S,A,B1}∣{B2,C,T}\{S,A,B_1\}|\{B_2,C,T\}
    A1: arcs
    ACAC and B1B2B_1B_2 identified, capacity 5+6=115+6=11
    R1: flow equals cut capacity, so by the max-flow min-cut theorem it is maximal

    A1: the restriction reduces the maximum flow by
    14−11=314-11=3 thousand parcels per hour

    Total for question 3: 7 marks

  4. 4
    A company moves goods from a factory SS to a depot TT through hubs. The directed arcs and their capacities (tonnes per hour) are SASA 9, SBSB 7, ACAC 6, ADAD 3, BCBC 2, BDBD 5, CTCT 7 and DTDT 8. An initial flow of 11 tonnes per hour uses S→A→C→TS\to A\to C\to T with 6 and S→B→D→TS\to B\to D\to T with 5.
    (a)
    Use flow augmentation from the initial flow to find a maximum flow, and prove that it is maximal.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: a route using only arcs with spare capacity, e.g. S→A→D→TS\to A\to D\to T (spare 3, 3, 3)
    A1: flow increased by 3 to 14

    M1: a second route, e.g.
    S→B→C→TS\to B\to C\to T (spare 2, 2, 1)
    A1: flow increased by 1 to 15

    A1: maximum flow 15

    R1: the cut
    {S,A,B,C,D}∣{T}\{S,A,B,C,D\}|\{T\}, with arcs CTCT and DTDT, has capacity 7+8=157+8=15, so by the max-flow min-cut theorem the flow is maximal
    Accept: the cut
    {S,A,B,C}∣{D,T}\{S,A,B,C\}|\{D,T\} with arcs ADAD, BDBD, CTCT and capacity 3+5+7=153+5+7=15
    (b)
    Hub DD can in fact process at most 6 tonnes per hour. The company can either raise the capacity of arc CTCT by 2, or raise the hub's limit by 2. Evaluate the two options, using cuts.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: hub DD modelled as D1→D2D_1\to D_2 with capacity 6, arcs into DD ending at D1D_1 and arcs out of DD leaving from D2D_2
    A1: minimum cut
    {CT,D1D2}\{CT,D_1D_2\}, capacity 7+6=137+6=13, so the maximum flow is now 13
    M1: considers the cuts again after each change

    A1: raising
    CTCT to 9 gives a minimum cut {AC,BC,D1D2}\{AC,BC,D_1D_2\} of capacity 6+2+6=146+2+6=14, so the maximum flow is only 14
    A1: raising
    DD to 8 gives a maximum flow of 15
    R1: raising the hub's limit increases the flow by 2 against 1, so it is the better option

    Accept: the cut
    {AC,BC,D1D2}\{AC,BC,D_1D_2\} written as {S,A,B,D1}∣{C,D2,T}\{S,A,B,D_1\}|\{C,D_2,T\}

    Total for question 4: 12 marks

End of questions

Subtopic tests