(a) 40+30+50+62+70+25+45+35=357\ \mathrm{m} [A1]
(b) degrees: \mathrm{J}_1\colon3, \mathrm{J}_2\colon3, \mathrm{J}_3\colon4, \mathrm{J}_4\colon3, \mathrm{J}_5\colon3 [A1]
four junctions have odd degree, so no closed route uses every corridor exactly once: some corridors are walked twice [R1]
(c) odd junctions \mathrm{J}_1, \mathrm{J}_2, \mathrm{J}_4, \mathrm{J}_5; six pairs, with routes through other junctions where shorter [M1]
\mathrm{J}_1\mathrm{J}_2=40, \mathrm{J}_2\mathrm{J}_5=25, \mathrm{J}_4\mathrm{J}_5=45, \mathrm{J}_1\mathrm{J}_4=62 [A1]
\mathrm{J}_1\mathrm{J}_5=65 (via \mathrm{J}_2), \mathrm{J}_2\mathrm{J}_4=70 (via \mathrm{J}_5) [A1]
(d) three ways to pair the four odd junctions [M1]
\mathrm{J}_1\mathrm{J}_2+\mathrm{J}_4\mathrm{J}_5=85; \ \mathrm{J}_1\mathrm{J}_4+\mathrm{J}_2\mathrm{J}_5=87; \ \mathrm{J}_1\mathrm{J}_5+\mathrm{J}_2\mathrm{J}_4=135 [A1]
the least extra distance is 85\ \mathrm{m}: repeat \mathrm{J}_1\mathrm{J}_2 and \mathrm{J}_4\mathrm{J}_5 [A1]
357+85=442\ \mathrm{m} [A1]
(e) she starts and finishes at two odd junctions, so only the shortest path between the other two is repeated: \mathrm{J}_2\mathrm{J}_5=25\ \mathrm{m} [R1]
start at \mathrm{J}_1 and finish at \mathrm{J}_4 (or the reverse) [A1]
357+25=382\ \mathrm{m} [A1]
(f) nearest neighbour from P: choose the shortest edge to an unvisited exhibit each time [M1]
route \mathrm{PQRSTP} with times 8,7,6,5,15 [A1]
upper bound 8+7+6+5+15=41 minutes [A1]
(g) delete P: minimum spanning tree of Q, R, S, T uses \mathrm{ST}=5, \mathrm{RS}=6, \mathrm{QR}=7 [M1]
total of the tree: 18 [A1]
add the two shortest edges at P, \mathrm{PQ}=8 and \mathrm{PS}=10: lower bound 36 minutes [A1]
(h) a tour that visits each exhibit once and returns to P, other than \mathrm{PQRSTP} [M1]
\mathrm{PQTSRP}=8+9+5+6+12=40 minutes [A1]
(i) adjacency matrix, with rows and columns in the order \mathrm{J}_1 to \mathrm{J}_5 []
\left(\begin{array}{ccccc}0&1&1&1&0\\1&0&1&0&1\\1&1&0&1&1\\1&0&1&0&1\\0&1&1&1&0\end{array}\right) [A1]
walks of length 2 from \mathrm{J}_1 to \mathrm{J}_5: entry (1,5) of the matrix squared, or a count of \mathrm{J}_1\to\mathrm{J}_k\to\mathrm{J}_5 [M1]
3 walks, through \mathrm{J}_2, \mathrm{J}_3 and \mathrm{J}_4 [A1]
(j) corridor length is not the same as time or effort, for example stairs, crowds or a gallery closed to cleaners [R1]
so the route of least length need not be the route of least cleaning time; times, or only the open corridors, should be used [R1]
Final answer
- (a) 357 m
- (b) 3,3,4,3,3
- (d) 442 m
- (e) \mathrm{J}_1 to \mathrm{J}_4, 382 m
- (f) 41
- (g) 36
- (h) 40
- (i) 3.