Further Mathematics · AQA 7367 · Option D · Topic DC

Network flows

Flows in networks: cuts, the maximum flow–minimum cut theorem and the labelling procedure.

  • 7 sub-topics
  • 4 in Year 12, 3 in Year 13
  • 105 practice questions
  • 7 animated lessons
Practice questions (105) Lessons Worksheets All AQA Further Mathematics topics

What the specification says

Every sub-topic AQA can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. DC1Flows in directed networksY12
  2. DC2Cuts and their valuesY12
  3. DC3Maximum flow–minimum cut theoremY12
  4. DC4Supersources and supersinksY12
  5. DC5Augment flows to find the maximum flowY13
  6. DC6Arcs with upper and lower capacitiesY13
  7. DC7Nodes of restricted capacityY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 105 questions in this topic, free, no account needed.

Flows in networks

Not needed for Year 12Easy

The maximum flow–minimum cut theorem · Year 13 · 1 mark

  1. What does the maximum flow–minimum cut theorem say?
    (1)

Show worked solutionHide worked solution
  1. So a flow is proved maximal by finding a cut whose capacity equals the value of the flow.A: The value of the maximum flow equals the capacity of the minimum cut

Total1

  • M
  • A
  • B
How did it go?

Report a problem with this question

Flows in networks

Not needed for Year 12Medium

Cuts · Year 13 · 4 marks

Figure 1 shows a directed network. The numbers are capacities.
1012114161491612SABCDT
Figure 1
  1. (a)
    Find the capacity of the cut that separates {A, B, D, S} from the other vertices.
    (2)
  2. (b)
    Find the capacity of the cut that separates {A, S} from the other vertices.
    (1)
  3. (c)
    What can you deduce about the maximum flow?
    (1)

Check your answers before you look at the solution

Show worked solutionHide worked solution

Part (a)2 marks

  1. Arcs from the sink side back to the source side count 0.Arcs from the source side to the sink side: AC, DT.
  2. 1616

Part (b)1 mark

  1. 4343

Part (c)1 mark

  1. It is at most 16, the smaller cut capacity.

Total4

  • M
  • A
  • B
How did it go?

Report a problem with this question

Flows in networks

Not needed for Year 12Hard

Finding a maximum flow · Year 13 · 6 marks

Figure 1 shows a directed network. The numbers are capacities.
1016181415161249SABCDT
Figure 1
  1. (a)
    Use the labelling procedure, or otherwise, to find a maximum flow. State the flow in each arc.
    (4)
  2. (b)
    Prove that your flow is maximal.
    (2)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)4 marks

  1. Find flow-augmenting routes until no more exist.
  2. A flow pattern; others with the same value are possible.SA: 10, SB: 3, AB: 0, AC: 10, AD: 0, BD: 3, CD: 6, CT: 4, DT: 9
  3. maximum flow=13\text{maximum flow} = 13

Part (b)2 marks

  1. The cut separating {A, B, C, D, S} from {T} has capacity 13.
  2. Max-flow = min-cut, so the flow is maximal.

Total6

  • M
  • A
  • B
How did it go?

Report a problem with this question