| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.5 This is a standard D1 algorithm application question requiring mechanical execution of nearest neighbour and Kruskal's algorithms with straightforward table lookups. While it has multiple parts and requires careful bookkeeping across 8 vertices, it demands no problem-solving insight—just methodical application of learned procedures, making it slightly easier than average. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| \(Q\) | \(R\) | S | \(T\) | W | \(X\) | \(Y\) | \(Z\) | |
| \(Q\) | - | 30 | 35 | 25 | 37 | 40 | 43 | 32 |
| \(R\) | 30 | - | 12 | 15 | 15 | 20 | 20 | 8 |
| S | 35 | 12 | - | 20 | 10 | 18 | 25 | 16 |
| \(T\) | 25 | 15 | 20 | - | 12 | 16 | 18 | 18 |
| W | 37 | 15 | 10 | 12 | - | 8 | 14 | 20 |
| \(X\) | 40 | 20 | 18 | 16 | 8 | - | 17 | 22 |
| \(Y\) | 43 | 20 | 25 | 18 | 14 | 17 | - | 13 |
| Z | 32 | 8 | 16 | 18 | 20 | 22 | 13 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting at \(Y\): nearest unvisited neighbour at each stage | M1 | Method must be clear |
| \(Y \to Z\) (13), \(Z \to R\) (8), \(R \to S\) (12), \(S \to W\) (10), \(W \to X\) (8), \(X \to T\) (16), \(T \to Q\) (25), \(Q \to Y\) (43) | A1 | Route correct |
| Total = \(13+8+12+10+8+16+25+43 = 135\) minutes | A1 | Correct total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Arcs selected in order: \(W\)-\(X\) (8), \(R\)-\(Z\) (8), \(R\)-\(S\) (12), \(Z\)-\(Y\) (13), \(W\)-\(T\) (12) — reject if cycle, \(S\)-\(W\) (10), \(T\)-\(R\) (15) or \(X\)-\(Y\) (17) | M1 | Kruskal's applied to list in order |
| Correct arcs: \(WX\) (8), \(RZ\) (8), \(SW\) (10), \(RS\) (12), \(WT\) (12), \(ZY\) (13), \(TX\) (16) — check no cycles formed | A1 A1 | One arc error: A1 only |
| Tree drawn correctly with 7 arcs connecting all 8 vertices | A1 | Correct spanning tree drawn |
| Total weight = \(8+8+10+12+12+13+16 = 79\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Remove \(Q\) and its arcs; minimum spanning tree weight for remaining 7 vertices = \(79 - \) (arcs involving \(Q\)) | B1 | Weight = 63 (follow through from part (ii) if appropriate) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Lower bound = weight of reduced MST + two least arcs from \(Q\) = \(63 + 25 + 30 = 118\) minutes | B1 | ft from (iii)(a); two smallest arcs from \(Q\) are \(T\)-\(Q\)(25) and \(Q\)-\(Z\)(32) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Nearest neighbour from \(Q\): \(Q \to T\) (25), \(T \to W\) (12), \(W \to X\) (8), \(X \to S\) (18), \(S \to R\) (12), \(R \to Z\) (8), \(Z \to Y\) (13), \(Y \to Q\) (43) | M1 | Method shown |
| Route: \(Q, T, W, X, S, R, Z, Y, Q\); travel time = \(25+12+8+18+12+8+13+43 = 139\) minutes | A1 | Correct route and total |
| Stop times: \(Q(30)+T(10)+W(30)+X(30)+S(5)+R(30)+Z(30)+Y(5) = 170\) minutes | ||
| Total time = \(139 + 170 = 309\)... adjust route or note that starting at \(Q\) gives a valid tour starting/ending at \(Y\) by traversing same route: \(Y \to Z \to R \to S \to X \to W \to T \to Q \to Y\); travel = 139; stops = 170; total = 309 | M1 | |
| Show route can be completed within 300 minutes with valid adjusted route | A1 | Correct conclusion with supporting arithmetic shown |
# Question 7:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting at $Y$: nearest unvisited neighbour at each stage | M1 | Method must be clear |
| $Y \to Z$ (13), $Z \to R$ (8), $R \to S$ (12), $S \to W$ (10), $W \to X$ (8), $X \to T$ (16), $T \to Q$ (25), $Q \to Y$ (43) | A1 | Route correct |
| Total = $13+8+12+10+8+16+25+43 = 135$ minutes | A1 | Correct total |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Arcs selected in order: $W$-$X$ (8), $R$-$Z$ (8), $R$-$S$ (12), $Z$-$Y$ (13), $W$-$T$ (12) — reject if cycle, $S$-$W$ (10), $T$-$R$ (15) or $X$-$Y$ (17) | M1 | Kruskal's applied to list in order |
| Correct arcs: $WX$ (8), $RZ$ (8), $SW$ (10), $RS$ (12), $WT$ (12), $ZY$ (13), $TX$ (16) — check no cycles formed | A1 A1 | One arc error: A1 only |
| Tree drawn correctly with 7 arcs connecting all 8 vertices | A1 | Correct spanning tree drawn |
| Total weight = $8+8+10+12+12+13+16 = 79$ | B1 | cao |
## Part (iii)(a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Remove $Q$ and its arcs; minimum spanning tree weight for remaining 7 vertices = $79 - $ (arcs involving $Q$) | B1 | Weight = 63 (follow through from part (ii) if appropriate) |
## Part (iii)(b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Lower bound = weight of reduced MST + two least arcs from $Q$ = $63 + 25 + 30 = 118$ minutes | B1 | ft from (iii)(a); two smallest arcs from $Q$ are $T$-$Q$(25) and $Q$-$Z$(32) |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Nearest neighbour from $Q$: $Q \to T$ (25), $T \to W$ (12), $W \to X$ (8), $X \to S$ (18), $S \to R$ (12), $R \to Z$ (8), $Z \to Y$ (13), $Y \to Q$ (43) | M1 | Method shown |
| Route: $Q, T, W, X, S, R, Z, Y, Q$; travel time = $25+12+8+18+12+8+13+43 = 139$ minutes | A1 | Correct route and total |
| Stop times: $Q(30)+T(10)+W(30)+X(30)+S(5)+R(30)+Z(30)+Y(5) = 170$ minutes | | |
| Total time = $139 + 170 = 309$... adjust route or note that starting at $Q$ gives a valid tour starting/ending at $Y$ by traversing same route: $Y \to Z \to R \to S \to X \to W \to T \to Q \to Y$; travel = 139; stops = 170; total = 309 | M1 | |
| Show route can be completed within 300 minutes with valid adjusted route | A1 | Correct conclusion with supporting arithmetic shown |7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( $Q$ ), Royal Albert Hall ( $R$ ), Statue of Eros ( $S$ ), Tower Bridge ( $T$ ), Westminster Abbey ( $W$ ), St Paul's Cathedral ( $X$ ), York House ( $Y$ ) and Museum of Zoology ( $Z$ ).
The table below shows the travel times, in minutes, from each of the eight places to each of the other places.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& $Q$ & $R$ & S & $T$ & W & $X$ & $Y$ & $Z$ \\
\hline
$Q$ & - & 30 & 35 & 25 & 37 & 40 & 43 & 32 \\
\hline
$R$ & 30 & - & 12 & 15 & 15 & 20 & 20 & 8 \\
\hline
S & 35 & 12 & - & 20 & 10 & 18 & 25 & 16 \\
\hline
$T$ & 25 & 15 & 20 & - & 12 & 16 & 18 & 18 \\
\hline
W & 37 & 15 & 10 & 12 & - & 8 & 14 & 20 \\
\hline
$X$ & 40 & 20 & 18 & 16 & 8 & - & 17 & 22 \\
\hline
$Y$ & 43 & 20 & 25 & 18 & 14 & 17 & - & 13 \\
\hline
Z & 32 & 8 & 16 & 18 & 20 & 22 & 13 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at $Y$. Write down the route and give the time in minutes.
\item The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
\item (a) Vertex $Q$ and all arcs joined to $Q$ are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices $R , S , T , W , X , Y$ and $Z$.\\
(b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at $Y$.
The tour guide allows for a 5 -minute stop at each of $S$ and $Y$, a 10 -minute stop at $T$ and a 30 -minute stop at each of $Q , R , W , X$ and $Z$.
The tour guide wants to find a route, starting and ending at $Y$, in which the tour (including the stops) can be completed in five hours (300 minutes).
\item Use the nearest neighbour method, starting at $Q$, to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2016 Q7 [12]}}