Moderate -0.3 This is a straightforward application of standard Decision Mathematics algorithms (MST and TSP) with a small network (5 vertices). Parts (i)-(ii) test basic understanding of graph concepts, part (iii) is routine MST application, and part (iv) requires checking only 3! = 6 possible routes through A, B, C. The conceptual difficulty is low and the computational work is minimal, making this slightly easier than an average A-level question.
4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places \(\mathrm { A } , \mathrm { B }\) and C (once each, in any order) and then finish at his own house (T).
Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk.
Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
(a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?
(b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem?
The distance matrix below shows the direct distances, in km , between places.
S
A
B
C
T
n S
0
3
2
5
4
nA
3
0
2
2.5
2
nB
2
2
0
3.2
2.5
n
5
2.5
3.2
0
2
\cline { 2 - 6 }
T
4
2
2.5
2
0
\cline { 2 - 6 }
\cline { 2 - 6 }
- Use an appropriate algorithm to find a minimum spanning tree for Tom's network.
OCR is committed to seeking permission to reproduce all third-party content that it uses in its assessment materials. OCR has attempted to identify and contact all copyright holders
whose work is used in this paper. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced in the OCR Copyright
Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download from our public website (www.ocr.org.uk) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible
opportunity.
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
OCR is part of the Cambridge Assessment Group; Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a
4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places $\mathrm { A } , \mathrm { B }$ and C (once each, in any order) and then finish at his own house (T).
\begin{enumerate}[label=(\roman*)]
\item Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk.
Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
\item (a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?\\
(b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem?
The distance matrix below shows the direct distances, in km , between places.
\begin{center}
\begin{tabular}{ l | c | c | c | c | c | }
& \multicolumn{1}{c}{S} & \multicolumn{1}{c}{A} & \multicolumn{1}{c}{B} & \multicolumn{1}{c}{C} & \multicolumn{1}{c}{T} \\
n S & 0 & 3 & 2 & 5 & 4 \\
nA & 3 & 0 & 2 & 2.5 & 2 \\
nB & 2 & 2 & 0 & 3.2 & 2.5 \\
n & 5 & 2.5 & 3.2 & 0 & 2 \\
\cline { 2 - 6 }
T & 4 & 2 & 2.5 & 2 & 0 \\
\cline { 2 - 6 }
& & & & & \\
\cline { 2 - 6 }
\end{tabular}
\end{center}
\item - Use an appropriate algorithm to find a minimum spanning tree for Tom's network.
\begin{itemize}
\item Give the total weight of the minimum spanning tree.
\item - Find the route that solves Tom's problem.
\item Give the minimum distance that Tom must walk.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR FD1 AS 2017 Q4 [8]}}