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.
Multiple Choice
15 questions drawn from the full module bank — feedback shown immediately
Short Answer
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 using Dijkstra's algorithm. (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
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
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
(a) Steps shown [1], MST edges correct [0.5], total = 9 [0.5].
(b) Dijkstra's table/working [1], shortest = 6 [1].
(c) Degrees calculated [1], conclusion (not possible for circuit) with justification [1].
(a) Paths and flows shown [2], total = 12 [1].
(b) Cut identified [1], verification [1].
(c) Correct pipe identified [1], justification [1].
(a) Proof by contradiction or induction [3].
(b) Derivation [2].
(c) Answer = 5 [1], explanation [1].
(d) Similarities [1.5], differences [1.5].
Tick when you have finished all questions and checked your answers.