| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 19 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Compare Multiple Upper Bounds |
| Difficulty | Easy -1.2 This is a standard D1 algorithm application question requiring routine execution of nearest neighbour and Prim's algorithms with minimal problem-solving. Parts (b)(iii), (c)(iii), and (d) involve simply selecting values from given lists and stating an interval, making this easier than average A-level maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { F }\) | G | |
| A | - | 2 | 6 | 4 | 16 | 27 |
| \(\boldsymbol { B }\) | 2 | - | 8 | 3 | 15 | 26 |
| \(\boldsymbol { C }\) | 6 | 8 | - | 10 | 22 | 32 |
| \(\boldsymbol { D }\) | 4 | 3 | 10 | - | 12 | 23 |
| \(\boldsymbol { F }\) | 16 | 15 | 22 | 12 | - | 20 |
| G | 27 | 26 | 32 | 23 | 20 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(E\) row/column values: \(AE\)=10, \(BE\)=8 (or equivalent shortest distances involving E) | B1 | One correct value |
| All E entries correct: \(EA=10, EB=8, EC=17, ED=4, EF=19, EG=19\) | B1 | All correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B \to A\) (2) | M1 | Correct first step |
| \(B \to A \to D\) (2+4=6) | A1 | |
| \(B \to A \to D \to F\) (6+12=18) | A1 | |
| \(B \to A \to D \to F \to G \to C \to E \to B\): total = \(2+4+12+20+32+17+8 = 77\) | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B \to A \to D \to F \to G \to C \to E \to B\) | B1 | Follow through |
| Correct corresponding actual path through network stated | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 76 miles | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Edges selected in order: \(AB\)(2), \(BD\)(3), \(DF\)(12), \(FG\)(20), \(AC\)(6) | M1 A1 | M1 method, A1 correct edges |
| Total MST = \(2+3+12+20+6 = 43\) | A1 | |
| Correct order of selection shown in table | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Delete \(A\); find two shortest edges at \(A\): \(AB=2\), \(AD=4\) | M1 | |
| MST of remaining vertices + two shortest edges from deleted vertex | M1 | |
| Lower bound = \(43 + 2 + 4 = \ldots\) (calculation shown) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 64 miles | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(64 \leq T \leq 76\) | B1 B1 | B1 for each correct bound |
# Question 7:
## Part (a): Complete Table 1
| Answer | Mark | Guidance |
|--------|------|----------|
| $E$ row/column values: $AE$=10, $BE$=8 (or equivalent shortest distances involving E) | B1 | One correct value |
| All E entries correct: $EA=10, EB=8, EC=17, ED=4, EF=19, EG=19$ | B1 | All correct |
## Part (b)(i): Nearest Neighbour from B
| Answer | Mark | Guidance |
|--------|------|----------|
| $B \to A$ (2) | M1 | Correct first step |
| $B \to A \to D$ (2+4=6) | A1 | |
| $B \to A \to D \to F$ (6+12=18) | A1 | |
| $B \to A \to D \to F \to G \to C \to E \to B$: total = $2+4+12+20+32+17+8 = 77$ | A1 | cao |
## Part (b)(ii): Sam's Actual Route
| Answer | Mark | Guidance |
|--------|------|----------|
| $B \to A \to D \to F \to G \to C \to E \to B$ | B1 | Follow through |
| Correct corresponding actual path through network stated | B1 | |
## Part (b)(iii): Best Upper Bound
| Answer | Mark | Guidance |
|--------|------|----------|
| 76 miles | B1 | cao |
## Part (c)(i): Prim's Algorithm from A (Table 2)
| Answer | Mark | Guidance |
|--------|------|----------|
| Edges selected in order: $AB$(2), $BD$(3), $DF$(12), $FG$(20), $AC$(6) | M1 A1 | M1 method, A1 correct edges |
| Total MST = $2+3+12+20+6 = 43$ | A1 | |
| Correct order of selection shown in table | A1 | |
## Part (c)(ii): Lower Bound
| Answer | Mark | Guidance |
|--------|------|----------|
| Delete $A$; find two shortest edges at $A$: $AB=2$, $AD=4$ | M1 | |
| MST of remaining vertices + two shortest edges from deleted vertex | M1 | |
| Lower bound = $43 + 2 + 4 = \ldots$ (calculation shown) | A1 | |
## Part (c)(iii): Best Lower Bound
| Answer | Mark | Guidance |
|--------|------|----------|
| 64 miles | B1 | cao |
## Part (d): Interval for T
| Answer | Mark | Guidance |
|--------|------|----------|
| $64 \leq T \leq 76$ | B1 B1 | B1 for each correct bound |7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools.\\
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392}
Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.
\begin{enumerate}[label=(\alph*)]
\item Complete Table 1.
\item \begin{enumerate}[label=(\roman*)]
\item On the completed Table 1, use the nearest neighbour algorithm, starting from $B$, to find an upper bound for the length of Sam's tour.
\item Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
\item Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76.
Write down the best upper bound.
7
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from $A$, to find a minimum spanning tree for the schools $A , B , C$, $D , F$ and $G$.
\item Hence find a lower bound for the length of Sam's minimum tour.
\item By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: $50,48,52,51,56$ and 64 .
Write down the best lower bound.
\end{enumerate}\item Given that the length of a minimum tour is $T$ miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know $T$ must lie.\\
(2 marks)
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Table 2}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { F }$ & G \\
\hline
A & - & 2 & 6 & 4 & 16 & 27 \\
\hline
$\boldsymbol { B }$ & 2 & - & 8 & 3 & 15 & 26 \\
\hline
$\boldsymbol { C }$ & 6 & 8 & - & 10 & 22 & 32 \\
\hline
$\boldsymbol { D }$ & 4 & 3 & 10 & - & 12 & 23 \\
\hline
$\boldsymbol { F }$ & 16 & 15 & 22 & 12 & - & 20 \\
\hline
G & 27 & 26 & 32 & 23 & 20 & - \\
\hline
\end{tabular}
\end{center}
\end{table}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q7 [19]}}