| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Complete Table by Inspection |
| Difficulty | Easy -1.2 This is a routine D1 question requiring inspection of a network diagram to find shortest paths between vertices and complete a distance table. It involves straightforward application of basic graph theory concepts with minimal problem-solving - students simply trace paths and compare distances. The 1-mark allocation confirms this is a standard, low-difficulty task. |
| Spec | 7.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 { E }\) | \(\boldsymbol { F }\) | |
| \(\boldsymbol { A }\) | - | 7 | ||||
| \(\boldsymbol { B }\) | 7 | - | 5 | |||
| \(\boldsymbol { C }\) | 5 | - | 4 | |||
| \(\boldsymbol { D }\) | 4 | - | 6 | |||
| \(\boldsymbol { E }\) | 6 | - | 10 | |||
| \(\boldsymbol { F }\) | 10 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A\)–\(C\) = 6, \(A\)–\(D\) = 5, \(A\)–\(E\) = 7 | B1 | Any two correct entries in row/column \(A\) |
| \(B\)–\(D\) = 9, \(B\)–\(E\) = 15, \(B\)–\(F\) = 12 | B1 | Remaining entries correct (by shortest paths) |
| \(C\)–\(E\) = 10, \(C\)–\(F\) = 12 | ||
| \(D\)–\(F\) = 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(AE + EF + FB + BC + CD + DA = 7 + 10 + 12 + 5 + 4 + 5 = 43\) | B1 | Must show working or state total = 43 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| It is a Hamiltonian cycle / visits all vertices, so the minimum journey cannot be longer than this | B1 | Must reference that it is a feasible route visiting all vertices |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| From \(D\): nearest unvisited is \(C\) (4) | M1 | Correct application of nearest neighbour from \(D\) |
| \(D \to C \to B\) (5) \(\to A\) (7) \(\to E\) (7) \(\to F\) (10) \(\to D\) (13) | A1 | Correct route identified |
| Total = \(4 + 5 + 7 + 7 + 10 + 13 = 46\) | A1 | Correct total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Delete \(A\) and find minimum spanning tree of remaining vertices \(B, C, D, E, F\) | M1 | Attempt to find MST of \(\{B,C,D,E,F\}\) |
| MST edges: \(CD = 4\), \(BC = 5\), \(DE = 6\), \(EF = 10\); total = 25 | A1 | Correct MST |
| Add two shortest edges from \(A\): \(AC = 6\) and \(AD = 5\) (or \(AE = 7\)) | M1 | Adding two least-weight edges incident to \(A\) |
| Lower bound = \(25 + 5 + 6 = 36\) | A1 | Correct lower bound = 36 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(36 \leq T \leq 43\) | B1 | Follow through from (b)(i), (c) and (d); must use minimum of upper bounds |
# Question 6:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A$–$C$ = 6, $A$–$D$ = 5, $A$–$E$ = 7 | B1 | Any two correct entries in row/column $A$ |
| $B$–$D$ = 9, $B$–$E$ = 15, $B$–$F$ = 12 | B1 | Remaining entries correct (by shortest paths) |
| $C$–$E$ = 10, $C$–$F$ = 12 | | |
| $D$–$F$ = 13 | | |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $AE + EF + FB + BC + CD + DA = 7 + 10 + 12 + 5 + 4 + 5 = 43$ | B1 | Must show working or state total = 43 |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| It is a Hamiltonian cycle / visits all vertices, so the minimum journey cannot be longer than this | B1 | Must reference that it is a feasible route visiting all vertices |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| From $D$: nearest unvisited is $C$ (4) | M1 | Correct application of nearest neighbour from $D$ |
| $D \to C \to B$ (5) $\to A$ (7) $\to E$ (7) $\to F$ (10) $\to D$ (13) | A1 | Correct route identified |
| Total = $4 + 5 + 7 + 7 + 10 + 13 = 46$ | A1 | Correct total |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Delete $A$ and find minimum spanning tree of remaining vertices $B, C, D, E, F$ | M1 | Attempt to find MST of $\{B,C,D,E,F\}$ |
| MST edges: $CD = 4$, $BC = 5$, $DE = 6$, $EF = 10$; total = 25 | A1 | Correct MST |
| Add two shortest edges from $A$: $AC = 6$ and $AD = 5$ (or $AE = 7$) | M1 | Adding two least-weight edges incident to $A$ |
| Lower bound = $25 + 5 + 6 = 36$ | A1 | Correct lower bound = 36 |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $36 \leq T \leq 43$ | B1 | Follow through from (b)(i), (c) and (d); must use minimum of upper bounds |
---6 The network shows the roads linking a warehouse at $A$ and five shops, $B , C , D , E$ and $F$. The numbers on the edges show the lengths, in miles, of the roads. A delivery van leaves the warehouse, delivers to each of the shops and returns to the warehouse.\\
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-12_1241_1239_484_402}
\begin{enumerate}[label=(\alph*)]
\item Complete the table, on the page opposite, showing the shortest distances between the vertices.
\item \begin{enumerate}[label=(\roman*)]
\item Find the total distance travelled if the van follows the cycle $A E F B C D A$.
\item Explain why your answer to part (b)(i) provides an upper bound for the minimum journey length.
\end{enumerate}\item Use the nearest neighbour algorithm starting from $D$ to find a second upper bound.
\item By deleting $A$, find a lower bound for the minimum journey length.
\item Given that the minimum journey length is $T$, write down the best inequality for $T$ that can be obtained from your answers to parts (b), (c) and (d).\\[0pt]
[1 mark]
\section*{Answer space for question 6}
REFERENCE\\
(a)
\begin{center}
\begin{tabular}{ | l | l | l | l | l | l | l | }
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ & $\boldsymbol { F }$ \\
\hline
$\boldsymbol { A }$ & - & 7 & & & & \\
\hline
$\boldsymbol { B }$ & 7 & - & 5 & & & \\
\hline
$\boldsymbol { C }$ & & 5 & - & 4 & & \\
\hline
$\boldsymbol { D }$ & & & 4 & - & 6 & \\
\hline
$\boldsymbol { E }$ & & & & 6 & - & 10 \\
\hline
$\boldsymbol { F }$ & & & & & 10 & - \\
\hline
\end{tabular}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2015 Q6 [12]}}