Flows, cuts and the max-flow min-cut theorem

Flows, cuts and the max-flow min-cut theorem Test

Spec DC1–DC3 · 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

Flows, cuts and the max-flow min-cut theorem

Total 27 marks

Name

Class

Date

  1. 1
    A network has source SS, sink TT and intermediate nodes AA and BB. The directed arcs and their capacities are SASA 7, SBSB 6, ABAB 2, ATAT 4 and BTBT 8.
    (a)
    Find the capacity of the cut that separates {S,B}\{S,B\} from {A,T}\{A,T\}.
    [1 mark]
    • A1313
    • B1515
    • C1717
    • D2727
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    What is the value of the maximum flow from SS to TT?
    [1 mark]
    • A1313
    • B1515
    • C88
    • D1212
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Explain why the flow from SS to TT cannot exceed 12.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: identifies the cut {S,A,B}∣{T}\{S,A,B\}|\{T\}, whose arcs are ATAT and BTBT with capacity 4+8=124+8=12
    R1: all flow from
    SS to TT must cross the cut, so it cannot exceed its capacity
    Accept: the cut
    {S,A}∣{B,T}\{S,A\}|\{B,T\}, with arcs SBSB, ABAB, ATAT and capacity 6+2+4=126+2+4=12

    Total for question 1: 4 marks

  2. 2
    Two factories F1F_1 and F2F_2 can make at most 10 and 8 tonnes of a product per hour. They send it through a depot DD to two shops T1T_1 and T2T_2, which can receive at most 8 and 6 tonnes per hour. The directed arcs and their capacities (tonnes per hour) are F1DF_1D 9, F2DF_2D 6, F1T1F_1T_1 3, DT1DT_1 5 and DT2DT_2 7.
    (a)
    A supersource SS is added so the network has a single source. Which arcs should be added?
    [1 mark]
    • AOne arc from SS to F1F_1 with capacity 18
    • BArcs from T1T_1 and T2T_2 to SS with capacities 8 and 6
    • CArcs from SS to F1F_1 and from SS to F2F_2 with capacities 10 and 8
    • DArcs from SS to T1T_1 and from SS to T2T_2 with capacities 8 and 6
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    A supersink is also added, using the shops' limits. What is the value of the maximum flow, in tonnes per hour?
    [1 mark]
    • A1414
    • B1212
    • C1515
    • D1818
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Explain why arc DT2DT_2 cannot be saturated in a maximum flow.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: T2T_2 can receive at most 6 tonnes per hour, so the flow along DT2DT_2 is at most 6
    R1: the capacity of
    DT2DT_2 is 7, so at least 1 tonne per hour of its capacity is always unused
    Accept: the arc from
    T2T_2 to the supersink has capacity 6

    Total for question 2: 4 marks

  3. 3
    A network has source SS, sink TT and nodes AA, BB and CC. The directed arcs and their capacities are SASA 10, SBSB 6, ABAB 3, ACAC 5, BCBC 4, BTBT 2 and CTCT 9.
    (a)
    Find the capacity of the cut that separates {S,B}\{S,B\} from {A,C,T}\{A,C,T\}.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: arcs from {S,B}\{S,B\} to {A,C,T}\{A,C,T\} identified as SASA, BCBC and BTBT
    M1: adds the capacities of arcs directed out of
    {S,B}\{S,B\} only
    A1:
    10+4+2=1610+4+2=16
    Do not accept: 19, from including
    ABAB, which is directed into {S,B}\{S,B\}
    (b)
    A flow of value 11 is found. Prove that it is a maximum flow.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: chooses a cut separating SS from TT, e.g. {S,A,B}∣{C,T}\{S,A,B\}|\{C,T\}
    A1: arcs
    ACAC, BCBC, BTBT identified
    A1: capacity
    5+4+2=115+4+2=11
    R1: flow value equals the capacity of a cut, so by the max-flow min-cut theorem the flow is maximal

    Accept: the cut
    {S,A,B,C}∣{T}\{S,A,B,C\}|\{T\} with arcs BTBT, CTCT, capacity 2+9=112+9=11

    Total for question 3: 7 marks

  4. 4
    A distributor has two warehouses W1W_1 and W2W_2 that can dispatch at most 14 and 10 pallets per day. Goods go through a hub HH to two stores M1M_1 and M2M_2, which can take at most 11 and 9 pallets per day. The directed arcs and their capacities (pallets per day) are W1HW_1H 8, W2HW_2H 7, W1M1W_1M_1 5, HM1HM_1 6, HM2HM_2 9 and W2M2W_2M_2 3.
    (a)
    A flow of 20 pallets per day is found. (i) Describe how to turn the network into one with a single source and a single sink, giving all capacities. (ii) Show that 20 is the maximum flow.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) supersource SS with arcs SW1SW_1 (14) and SW2SW_2 (10)
    B1: (i) supersink
    ZZ with arcs M1ZM_1Z (11) and M2ZM_2Z (9)
    M1: (ii) a cut separating
    ZZ from the rest, using arcs M1ZM_1Z and M2ZM_2Z
    A1: capacity
    11+9=2011+9=20
    R1: every unit of flow from
    SS to ZZ crosses this cut, so the flow cannot exceed 20
    R1: the flow equals the cut capacity, so by the max-flow min-cut theorem it is a maximum

    Accept: the cut
    {S,W1,W2,H,M2}∣{M1,Z}\{S,W_1,W_2,H,M_2\}|\{M_1,Z\} with arcs W1M1W_1M_1, HM1HM_1, M2ZM_2Z and capacity 5+6+9=205+6+9=20
    (b)
    The distributor can raise the capacity of exactly one arc of the original network (including the arcs to the supersink) by 3. Using cuts, decide which arc to raise, and find the new maximum flow.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: finds the minimum cuts of the network with the supersource and supersink
    A1:
    {M1Z,M2Z}\{M_1Z,M_2Z\} and {W1M1,HM1,M2Z}\{W_1M_1,HM_1,M_2Z\}, both of capacity 20
    R1: the maximum flow rises only if the arc lies in every minimum cut

    A1:
    M2ZM_2Z is the only arc in both, so raise M2ZM_2Z to 12
    M1: checks the next smallest cut, e.g.
    {HM2,W2M2,M1Z}\{HM_2,W_2M_2,M_1Z\}, capacity 9+3+11=239+3+11=23
    A1: new maximum flow 23, an increase of 3

    Accept: raising any other arc leaves one minimum cut unchanged, so the flow stays at 20

    Total for question 4: 12 marks

End of questions

Subtopic tests