Full Marks

A-level Further Maths Year 13 · Topic 8

Decision mathematics

A level decision maths optimises flows, games and allocations.

We will find maximum flows, use the simplex algorithm, and solve zero-sum games.

Then we tackle the travelling salesperson and allocation problems.

In this topic

  1. 8.1Network flows: maximum flow and minimum cutFree below · 15 questions
  2. 8.2Linear programming: the simplex algorithmOpen in Full Marks · 14 questions
  3. 8.3Game theory: zero-sum games, stable solutions and mixed strategiesOpen in Full Marks · 14 questions
  4. 8.4The travelling salesperson problem: upper and lower boundsOpen in Full Marks · 14 questions
  5. 8.5Allocation and transportation problemsOpen in Full Marks · 15 questions

8.1 · Free notes

Network flows: maximum flow and minimum cut

Key points

In more detail

Practice

Network flows: maximum flow and minimum cut: 10 questions

Pick an answer to check it, or open the answer for the explanation.

1. What does the max-flow min-cut theorem state?

  1. Maximum flow = total capacity
  2. Minimum cut = 0
  3. Flow in = capacity
  4. Maximum flow = capacity of the minimum cut
Show answer

D: Maximum flow = capacity of the minimum cut. A key result.

2. Which arcs count towards the capacity of a cut?

  1. All arcs crossing the cut
  2. Arcs from the source side to the sink side
  3. Arcs from the sink side to the source side
  4. Only arcs at S
Show answer

B: Arcs from the source side to the sink side. Backward arcs do not count.

3. What condition holds at an intermediate vertex in a feasible flow?

  1. Flow in = flow out
  2. Flow in > flow out
  3. Flow out = 0
  4. Flow = capacity
Show answer

A: Flow in = flow out. Conservation of flow.

4. If a cut has capacity 12, what can you say about the maximum flow?

  1. It is exactly 12
  2. It is at least 12
  3. It is at most 12
  4. It is 0
Show answer

C: It is at most 12. Every cut is an upper bound.

5. What is a flow-augmenting path?

  1. The shortest path
  2. A cut
  3. A path with zero capacity
  4. A path from S to T along which the flow can be increased
Show answer

D: A path from S to T along which the flow can be increased. Uses spare capacity or reduces backward flows.

6. How are multiple sources handled?

  1. Delete all but one
  2. Add a super-source joined to each source
  3. Add a sink
  4. Ignore them
Show answer

B: Add a super-source joined to each source. With suitable capacities.

7. How is a capacity on a vertex modelled?

  1. Split the vertex into two joined by an arc with that capacity
  2. Delete the vertex
  3. Double its arcs
  4. Add a super-sink
Show answer

A: Split the vertex into two joined by an arc with that capacity. Standard technique.

8. A flow of 15 is found and a cut of capacity 15 exists. What do you conclude?

  1. More flow is possible
  2. The cut is wrong
  3. The flow of 15 is maximal
  4. Nothing
Show answer

C: The flow of 15 is maximal. By max-flow min-cut.

9. Can flow along an arc exceed its capacity?

  1. Yes
  2. Only at the sink
  3. Only backwards
  4. No
Show answer

D: No. Feasibility condition.

10. What does a backward flow in the labelling procedure represent?

  1. Flow into the source
  2. Flow that can be cancelled (reduced)
  3. Negative capacity
  4. An error
Show answer

B: Flow that can be cancelled (reduced). It lets the algorithm reroute flow.

Keep going in Full Marks

Full Marks has 15 questions on Network flows: maximum flow and minimum cut (5 more than here), set out in practice levels. You also get notes and 3D models for all 5 subtopics of Decision mathematics, plus games, timed exams and past papers.

Practise 8.1 in Full MarksOpen Decision mathematics

On your exam board

Not in the Cambridge specification.

All A-level Further Maths Year 13 topics