Year 12 Maths Standard Checkpoint 2 ~25 min

Checkpoint 2: Network Optimisation

Covers Lessons 7–12: minimum spanning trees, shortest paths, maximum flow, and mixed network problems.

🏁
Know

Key Facts

  • Kruskal's and Prim's steps
  • The shortest-path method
  • Max-flow min-cut theorem
Understand

Concepts

  • When to use each algorithm
  • Why MST ≠ shortest path
  • Flow conservation
Can Do

Skills

  • Apply all algorithms
  • Identify problem types
  • Solve multi-part questions

Multiple Choice

MC

Revision Multiple Choice

Question set not yet written, use the module quiz for now

This checkpoint is not available yet.

Its question set has not been written, so there is nothing here to attempt. Nothing you have done is lost, and the lessons either side of it are unaffected.

To test yourself on this material now, use the module quiz, which covers the same content.

Short Answer

📝

Extended Questions

Beyond the syllabus. This is the Year 12 Network Optimisation checkpoint, and part (c) of question 1 asks for a maximum flow. Maximum flow is outside Networks, paths and trees (MST-11-07) and will not be assessed in Year 11, so answer parts (a) and (b) and stop. Those two are examinable and are worth doing: (a) is a minimal-connector problem solved with a minimum spanning tree, and (b) is a shortest path on a network of well under ten vertices, which is exactly the depth the exam asks for.
ApplyBand 4

1. Network: AB=5, AC=2, BC=3, BD=4, CD=1, CE=6, DE=3. (a) Find MST using Kruskal's. (b) Find the shortest path from A to E. (c) If directed A→B(5), A→C(2), B→C(3), B→D(4), C→D(1), C→E(6), D→E(3), find max flow A→E. 4 MARKS

Answer in your workbook
AnalyseBand 5

2. (a) Explain why Prim's and Kruskal's always find MSTs with the same total weight. (b) A student finds an MST of weight 20 and claims the shortest path between two vertices in this MST is also 20. Explain the error. (c) In a max flow problem, if all edge capacities are integers, must the max flow be an integer? Explain. 3 MARKS

Answer in your workbook

Comprehensive Answers

▼

Short Answer Model Answers

Q1 (4 marks): (a) MST edges and total = 9 [1.5]. (b) Shortest path = 6 [1]. (c) Max flow = 7 [1.5].

Q2 (3 marks): (a) Explanation [1]. (b) Error explained [1]. (c) Yes with reason [1].

Mark checkpoint as complete

Tick when you have finished all questions and checked your answers.

Module overview · Maths Standard subject page · Module Quiz