Further Mathematics · Pearson Edexcel 9FM0 · Option D2 · Topic 3

Flows in networks

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

  • 5 sub-topics
  • Taught in Year 13
  • 77 practice questions
  • 5 animated lessons
Practice questions (77) Lessons Worksheets All Edexcel Further Mathematics topics

What the specification says

Every sub-topic Pearson Edexcel 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. 3.1CutsY13
  2. 3.2Labelling procedureY13
  3. 3.3Max-flow min-cut theoremY13
  4. 3.4Supersources, supersinks and vertex capacitiesY13
  5. 3.5Upper and lower capacitiesY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 77 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