Cuts, labelling procedure and max-flow min-cut

Cuts, labelling procedure and max-flow min-cut Test

Spec 3.1–3 · 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

Cuts, labelling procedure and max-flow min-cut

Total 27 marks

Name

Class

Date

  1. 1
    A network has source S, sink T and intermediate vertices A and B. The directed arcs and their capacities are: SA 7, SB 5, AB 3, AT 4 and BT 6 (for example, arc SA goes from S to A and has capacity 7).
    (a)
    What is the capacity of the cut that separates {S,A}\{S,A\} from {B,T}\{B,T\}?
    [1 mark]
    • A88
    • B1919
    • C2525
    • D1212
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    A flow has SA 5, SB 3, AB 1, AT 4 and BT 4. What is the value of this flow?
    [1 mark]
    • A55
    • B1010
    • C88
    • D1212
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    A flow of value 1010 is found: SA 7, SB 3, AB 3, AT 4 and BT 6. Use a cut to prove that this flow is a maximum flow.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: cut X={S,A,B}X=\{S,A,B\}, Y={T}Y=\{T\} with capacity AT ++ BT =4+6=10=4+6=10
    B1: the flow value equals the capacity of this cut, so by the max-flow min-cut theorem the flow is maximum

    Do not accept: a cut with capacity greater than
    1010

    Total for question 1: 4 marks

  2. 2
    A network has source S, sink T and intermediate vertices A, B and C. The directed arcs and their capacities are: SA 9, SB 7, AB 4, AC 5, BC 6, BT 4 and CT 8. A flow is already in the network: SA 5, SB 3, AB 2, AC 3, BC 3, BT 2 and CT 6, so the flow value is 8.
    (a)
    By how much can the flow along arc AC be increased?
    [1 mark]
    • A33
    • B22
    • C55
    • D88
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    In the labelling procedure, which pair of labels is written on arc SB?
    [1 mark]
    • A44 in the direction S to B and 33 in the direction B to S
    • B33 in the direction S to B and 44 in the direction B to S
    • C77 in the direction S to B and 33 in the direction B to S
    • D44 in the direction S to B and 44 in the direction B to S
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Find the amount by which the flow can be increased along the route S, A, C, T, and state the new flow value.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: spare capacities SA 44, AC 22, CT 22, so the flow increases by 22
    B1: new flow value
    8+2=108+2=10
    Accept: labels
    44, 22, 22 shown on the route

    Total for question 2: 4 marks

  3. 3
    A network has source S, sink T and intermediate vertices A, B, C and D. The directed arcs and their capacities are: SA 10, SB 8, AC 7, BA 3, BD 6, CT 9, DC 4 and DT 5.
    (a)
    Find the capacity of the cut that separates {S,A,C}\{S,A,C\} from {B,D,T}\{B,D,T\}, and of the cut that separates {S,A,B}\{S,A,B\} from {C,D,T}\{C,D,T\}. What do these tell you about the maximum flow?
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: first cut: arcs SB and CT from XX to YY, capacity 8+9=178+9=17 (BA and DC are directed from YY to XX and are not counted)
    B1: second cut: arcs AC and BD, capacity
    7+6=137+6=13
    B1: the maximum flow is at most
    1313
    Do not accept: counting arcs directed from
    YY to XX
    (b)
    A flow has SA 7, SB 5, AC 7, BD 5, CT 7 and DT 5, and zero flow on BA and DC. Use the labelling procedure to find a flow-augmenting route, increase the flow, and prove that the new flow is a maximum.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: labelling gives a route S, B, D, C, T using spare capacities SB 33, BD 11, DC 44 (forward), CT 22
    A1: flow increased by
    11, so the new flow value is 12+1=1312+1=13
    M1: the flow value
    1313 equals the capacity of the cut {S,A,B}\{S,A,B\}, {C,D,T}\{C,D,T\} found in (a)
    R1: so by the max-flow min-cut theorem the flow is maximum

    Accept: another route that reaches the same total

    Total for question 3: 7 marks

  4. 4
    A network has source S, sink T and intermediate vertices A, B, C and D. The directed arcs and their capacities are: SA 9, SB 8, AB 3, AD 3, BC 4, BD 3, BT 8, CT 11 and DT 5. A flow of value 3 is already in the network, with a flow of 3 along each of SA, AB, BD and DT, and zero flow elsewhere.
    (a)
    Use the labelling procedure to find the maximum flow, stating each flow-augmenting route and the amount by which the flow increases.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: a valid first route using forward spare capacity only, for example S, B, T
    A1: correct amount, for example
    88 (flow now 1111)
    M1: a second valid route, for example S, A, D, T

    M1: a route using the backward label on BD, that is reducing the flow in BD, for example S, A, D, B, C, T

    A1: its amount
    11 (after the routes above)
    A1: maximum flow
    1414
    Accept: any valid order of routes, if a route uses the backward arc DB and the total is
    1414
    (b)
    (i) Prove that the flow in (a) is a maximum flow. (ii) The owner can pay to increase the capacity of either CT from 1111 to 1515, or SB from 88 to 1010. Evaluate which, if either, is worth doing.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) cut X={S,A}X=\{S,A\}, Y={B,C,D,T}Y=\{B,C,D,T\} using arcs SB, AB, AD
    A1: capacity
    8+3+3=148+3+3=14, equal to the flow, so the flow is maximum (max-flow min-cut)
    B1: (ii) CT is not directed from
    XX to YY in this cut, so increasing it leaves the cut capacity, and so the maximum flow, at 1414
    M1: increasing SB by
    22 raises this cut to 10+3+3=1610+3+3=16
    A1: the next smallest cut has capacity at least
    1616 (for example {S,A,B,D}\{S,A,B,D\} has 4+8+5=174+8+5=17), so the maximum flow rises to 1616
    R1: increasing SB is worthwhile (flow up by
    22); increasing CT gives no benefit
    Accept: any valid argument that the minimum cut has become
    1616

    Total for question 4: 12 marks

End of questions

Subtopic tests