| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2017 |
| Session | Specimen |
| Marks | 13 |
| Topic | Travelling Salesman |
| Type | Apply Prim's Algorithm |
| Difficulty | Moderate -0.5 This is a standard Further Maths Discrete question testing routine application of TSP algorithms (MST for lower bound, nearest neighbour for upper bound). All steps are algorithmic with no novel problem-solving required, though it requires careful execution across multiple parts. Slightly easier than average A-level due to its procedural nature. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | |
| A | - | 12 | 8 | 6 | 4 |
| B | 12 | - | 10 | 8 | 10 |
| C | 8 | 10 | - | 13 | 10 |
| D | 6 | 8 | 13 | - | 10 |
| E | 4 | 10 | 10 | 10 | - |
| A | B | C | D | E | |
| F | 2 | 11 | 9 | 7 | 5 |
Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F. She wants to find a suitable route that does not involve her driving too far.
\begin{enumerate}[label=(\roman*)]
\item Which standard network problem does Fiona need to solve? [1]
\end{enumerate}
The shortest distances between clients, in km, are given in the matrix below.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& A & B & C & D & E \\
\hline
A & - & 12 & 8 & 6 & 4 \\
\hline
B & 12 & - & 10 & 8 & 10 \\
\hline
C & 8 & 10 & - & 13 & 10 \\
\hline
D & 6 & 8 & 13 & - & 10 \\
\hline
E & 4 & 10 & 10 & 10 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. [4]
\end{enumerate}
The distance from Fiona's house to each client, in km, is given in the table below.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& A & B & C & D & E \\
\hline
F & 2 & 11 & 9 & 7 & 5 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{2}
\item Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route. [2]
\item \begin{enumerate}[label=(\alph*)]
\item Find all the cycles that result from using the nearest neighbour method, starting at F. [3]
\item Use these to find an upper bound for the length of Fiona's route. [2]
\end{enumerate}
\item Fiona wants to drive less than 35 km. Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length. [1]
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2017 Q1 [13]}}