Mathematics Standard • Year 12 • Module 5 • Lesson 12
Module Review, Past-Paper Style
Practise HSC-style short and extended responses that draw on the whole Networks and Paths module.
1. Short-answer questions
1.1 (a) A connected network has 9 vertices and 12 edges. How many edges must be removed to form a spanning tree? (b) A complete graph K_n has 36 edges; find n. (c) A graph has degrees 5, 5, 4, 4, 4, 4. Does it have an Eulerian circuit? 3 marks Band 3
1.2 Find the maximum flow from S to T in the network with directed capacities S → A(8), S → B(5), A → B(3), A → C(4), B → C(2), B → T(6), C → T(7). Show paths and bottlenecks, then identify a minimum cut. 3 marks Band 3-4
1.3 An undirected weighted network on five towns has AB = 4, AC = 2, AD = 6, BC = 3, BD = 5, BE = 7, CD = 1, CE = 4, DE = 3. (a) Find MST using Kruskal's. (b) Find shortest A → E using Dijkstra's. (c) Find a Hamiltonian cycle from A or explain why none exists. 4 marks Band 4
Stuck on 1.3(c)? Try a cycle that uses cheap edges: A → C → D → E → B → A and check each edge exists.2. Extended response
2.1 A water authority manages a network linking a reservoir S, three pumping stations A, B, C, and a town T. Pipe data are given in the table (entries are capacities in ML/day; for the undirected MST and shortest-path questions, treat the same numbers as edge weights):
| S | A | B | C | T | |
|---|---|---|---|---|---|
| S | 8 | 5 | |||
| A | 8 | 3 | 4 | ||
| B | 5 | 3 | 2 | 6 | |
| C | 4 | 2 | 7 | ||
| T | 6 | 7 |
(a) MST. Treat the numbers as undirected weights ($thousand per km of pipe). Find the MST using Kruskal's or Prim's and state its total cost.
(b) Shortest path. Find the shortest S → T distance (still undirected) and the route.
(c) Max flow. Now treat the numbers as directed capacities (S → A, S → B, A → B, A → C, B → C, B → T, C → T; ignore reverse edges). Find the max flow S → T, identify a minimum cut, and write a one-sentence conclusion stating which infrastructure question would be answered by which calculation (MST vs shortest path vs max flow). 7 marks Band 5-6
Explicit marking criteria
Part (a), 2 marks
• 1 mark correct MST edges.
• 1 mark correct total cost with units.
Part (b), 2 marks
• 1 mark Dijkstra label table or equivalent working.
• 1 mark correct shortest distance and route.
Part (c), 3 marks
• 1 mark correct max flow with paths shown.
• 1 mark minimum cut identified and matched.
• 1 mark explicit conclusion mapping the three calculations to three management questions.
Your response:
Stuck on (c)? Three different optimisations on the same numbers, be careful to use directed edges for max flow only.How did this worksheet feel?
What I'll revisit before next class:
1.1, Spanning trees, K_n edges, Eulerian (3 marks)
Sample response. (a) Spanning tree has n − 1 = 8 edges; remove 12 − 8 = 4 edges. (b) n(n − 1)/2 = 36 ⇒ n(n − 1) = 72; n = 9 since 9 × 8 = 72. So n = 9. (c) Degrees 5, 5, 4, 4, 4, 4 has two odd vertices ⇒ no Eulerian circuit (would need all even); an Eulerian trail does exist.
Marking notes. 1 mark each part.
1.2, Max flow + min cut (3 marks)
Sample response.
Push S → A → C → T: min(8, 4, 7) = 4. Remaining S→A = 4, A→C = 0, C→T = 3.
Push S → B → T: min(5, 6) = 5. Remaining S→B = 0, B→T = 1.
Push S → A → B → C → T: min(4, 3, 2, 3) = 2. Remaining S→A = 2, A→B = 1, B→C = 0, C→T = 1.
Push S → A → B → T: min(2, 1, 1) = 1.
Total max flow = 4 + 5 + 2 + 1 = 12 ML/day.
Min cut {S, A} | {B, C, T}: S→B(5) + A→B(3) + A→C(4) = 12 ✓.
Marking notes. 1 mark, paths and bottlenecks. 1 mark, max flow = 12. 1 mark, matching min cut identified.
1.3, MST, shortest path, Hamiltonian (4 marks)
Sample response.
(a) Kruskal's. Sort: CD(1), AC(2), BC(3), DE(3), AB(4), CE(4), BD(5), AD(6), BE(7). Add CD, AC, BC (→ {A,B,C,D}), DE (→ {A,B,C,D,E}). MST = CD, AC, BC, DE; total = 1 + 2 + 3 + 3 = 9.
(b) Dijkstra from A. A = 0. Visit A: B = 4, C = 2, D = 6. Visit C (2): B = min(4, 5) = 4, D = min(6, 3) = 3, E = 6. Visit D (3): E = min(6, 6) = 6. Visit B (4): E = min(6, 11) = 6. Visit E (6). Shortest A → E = 6; path A → C → E or A → C → D → E.
(c) Try A → C → D → E → B → A: edges AC(2), CD(1), DE(3), EB(7), BA(4). All exist. Hamiltonian cycle: A → C → D → E → B → A, total = 17.
Marking notes. (a) 1.5 marks. (b) 1.5 marks. (c) 1 mark (cycle found, all edges checked).
2.1, Water authority network (7 marks): sample Band-6 response with annotations
Sample Band-6 response.
(a) MST (Kruskal's).
Edges (undirected): SA(8), SB(5), AB(3), AC(4), BC(2), BT(6), CT(7). Sort: BC(2), AB(3), AC(4), SB(5), BT(6), CT(7), SA(8). Add BC(2) → {B,C}. Add AB(3) → {A,B,C}. Reject AC(4), cycle. Add SB(5) → {S,A,B,C}. Add BT(6) → {S,A,B,C,T}. Stop (4 edges = 5 − 1). [1 mark, MST edges.]
MST = BC, AB, SB, BT; total = 2 + 3 + 5 + 6 = $16 thousand. [1 mark, correct total.]
(b) Shortest S → T (Dijkstra's).
S = 0. Visit S: A = 8, B = 5. Visit B (5): A = min(8, 8) = 8, C = 7, T = 11. Visit C (7): A no improvement, T = min(11, 14) = 11. Visit A (8): no improvement. Visit T (11). [1 mark, Dijkstra working.]
Shortest S → T = 11 km; route S → B → T (5 + 6 = 11). [1 mark, distance and route.]
(c) Max flow S → T (directed).
Directed edges: S → A(8), S → B(5), A → B(3), A → C(4), B → C(2), B → T(6), C → T(7).
Path S → A → C → T: min(8, 4, 7) = 4. Remaining S→A = 4, A→C = 0, C→T = 3.
Path S → B → T: min(5, 6) = 5. Remaining S→B = 0, B→T = 1.
Path S → A → B → C → T: min(4, 3, 2, 3) = 2. Remaining S→A = 2, A→B = 1, B→C = 0, C→T = 1.
Path S → A → B → T: min(2, 1, 1) = 1.
Total max flow = 4 + 5 + 2 + 1 = 12 ML/day. [1 mark, paths and bottlenecks correct.]
Min cut: {S, A} | {B, C, T} = S→B(5) + A→B(3) + A→C(4) = 12 ✓ = max flow. [1 mark, min cut matches max flow.]
Conclusion: the three calculations answer three different management questions on the same network, MST = $16k tells the authority the cheapest cable cost to keep all sites connected; shortest path S → T = 11 km tells maintenance crews the fastest direct route from reservoir to town; max flow = 12 ML/day tells operators the maximum throughput under normal directed flow. Mixing them up would either over-build infrastructure or under-deliver water. [1 mark, explicit conclusion mapping each calculation to its management question.]
Total: 7/7.
Band descriptors for marker.
Band 3: Attempts MST and one other part with arithmetic errors; max flow not started or incorrect. ≈ 3 marks.
Band 4: MST and shortest path correct; max flow attempted with valid paths but missing one path or no min cut. ≈ 4-5 marks.
Band 5: All three correct numerically; conclusion is shallow or just bare numbers. ≈ 6 marks.
Band 6: All three correct with explicit one-sentence conclusion mapping calculations to real management questions and warning against mixing them up. 7/7.