Year 12 Maths Standard Module 5 Quiz ~40 min

Module 5 Quiz: Networks and Paths

Full module assessment covering all twelve lessons: network terminology, paths and cycles, Eulerian and Hamiltonian routes, trees, adjacency matrices, minimum spanning trees, shortest paths, maximum flow, and mixed problems.

📝
Know

Key Facts

  • All definitions
  • Algorithm steps
  • Theorems and conditions
Understand

Concepts

  • Relationships between concepts
  • When to apply each algorithm
  • Proofs and justifications
Can Do

Skills

  • Solve all problem types
  • Show full working
  • Interpret word problems

Multiple Choice

MC

Multiple Choice

15 questions drawn from the full module bank, feedback shown immediately

Short Answer

📝

Extended Response

ApplyBand 4

1. A network has vertices A, B, C, D, E with edges: AB=4, AC=2, AD=6, BC=3, BD=5, BE=7, CD=1, CE=4, DE=3. (a) Find the MST using Kruskal's algorithm, showing each step. (2 marks) (b) Find the shortest path from A to E. (2 marks) (c) A postman must walk every edge exactly once, starting and ending at A. Is this possible? Justify your answer. (2 marks) 6 MARKS

Answer in your workbook
Beyond the syllabus. Question 2 below, the water distribution network, asks for a maximum flow and a minimum cut. Maximum flow is outside Networks, paths and trees (MST-11-07), so it will not be assessed in Year 11 and you can skip all seven marks of it. This is a legacy twelve-lesson Year 12 quiz; the parts of it that are examinable, and worth your time, are network terminology, constructing and interpreting a network diagram from a table or map, trees and spanning trees, minimal connectors, and identifying a shortest path.
AnalyseBand 5

2. A water distribution network has source S, sink T, and intermediate nodes A, B, C. Capacities (ML/day): S→A(8), S→B(5), A→B(3), A→C(4), B→C(2), B→T(6), C→T(7). (a) Find the maximum flow from S to T. Show your working. (3 marks) (b) Identify a minimum cut and verify the max-flow min-cut theorem. (2 marks) (c) The council plans to upgrade one pipe. Which pipe should they upgrade to maximise the increase in flow? Justify. (2 marks) 7 MARKS

Answer in your workbook
EvaluateBand 6

3. (a) Prove that a connected graph with n vertices and n-1 edges is a tree. (3 marks) (b) A complete graph Kₙ has every pair of vertices connected by an edge. Show that Kₙ has n(n-1)/2 edges. (2 marks) (c) A network has 6 vertices. What is the maximum number of edges it can have without containing a cycle? Explain. (2 marks) (d) Compare and contrast the MST problem and the shortest path problem. In what ways are they similar, and in what ways do they differ? (3 marks) 10 MARKS

Answer in your workbook

Comprehensive Answers

▼

Question 1 (6 marks)

(a) Steps shown [1], MST edges correct [0.5], total = 9 [0.5].

(b) Shortest-path table/working [1], shortest = 6 [1].

(c) Degrees calculated [1], conclusion (not possible for circuit) with justification [1].

Question 2 (7 marks)

(a) Paths and flows shown [2], total = 12 [1].

(b) Cut identified [1], verification [1].

(c) Correct pipe identified [1], justification [1].

Question 3 (10 marks)

(a) Proof by contradiction or induction [3].

(b) Derivation [2].

(c) Answer = 5 [1], explanation [1].

(d) Similarities [1.5], differences [1.5].

Mark quiz as complete

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

Module overview · Maths Standard subject page