| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.3 This is a multi-part question testing standard algorithmic procedures (Floyd's algorithm, nearest neighbour, minimum spanning tree) with straightforward application. While it has many parts, each step follows a mechanical procedure with no novel insight required. The route extraction and interpretation are routine for D2 students who have practiced these algorithms. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.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 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Distances \(1\to1\) and \(1\to2\) correct | M1 | distances \(1\to1\) and \(1\to2\) |
| Rest of first distance matrix correct | A2 | rest OK |
| Route \(5\to2\) correct | M1 | route \(5\to2\) |
| Rest of route matrix correct | A2 | rest OK |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(5 \to 1 \to 4 \to 2\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Complete graph drawn including loops | M1 | complete, inc loops |
| Correct answer (cao) | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(4\to(2)\to1\to(3)\to5\to(8)\to2\to(7)\to3\to(6)\to4\); Length = 26 | M1, A1, B1 | \(4\to1\to5\); complete, inc return to 4; cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(4\to1\to5\to(1\to4)\to2\to3\to4\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting at 1, 2 or 5 gives an HC of length 24. | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 3-arc connector found | M1 | 3-arc connector |
| Value = 15 | A1 | 15 |
| lower bound \(= 15 + 2 + 3 = 20\) | B1 | \(+2+3\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Odd vertices are 1, 2, 3, 5 identified | ||
| Pairings: \((1,2)\) and \((3,5)\): \(5+9=14\); \((1,3)\) and \((2,5)\): \(8+8=16\); \((1,5)\) and \((2,3)\): \(3+7=10\) | M1 | must have indication of pairing odd vertices |
| Min length \(= 43 + 3 + 7 = 53\) | A1 | cao |
| e.g. route \(\mathbf{1\ 5\ 1\ 2\ 3\ 2\ 4\ 3\ 5\ 4\ 1}\) | B1 | cao |
## Question 3:
### Part (i)(A)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Distances $1\to1$ and $1\to2$ correct | M1 | distances $1\to1$ and $1\to2$ |
| Rest of first distance matrix correct | A2 | rest OK |
| Route $5\to2$ correct | M1 | route $5\to2$ |
| Rest of route matrix correct | A2 | rest OK |
**Total: [6]**
### Part (i)(B)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $5 \to 1 \to 4 \to 2$ | B1 | cao |
**Total: [1]**
### Part (i)(C)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Complete graph drawn including loops | M1 | complete, inc loops |
| Correct answer (cao) | A1 | cao |
**Total: [2]**
### Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $4\to(2)\to1\to(3)\to5\to(8)\to2\to(7)\to3\to(6)\to4$; Length = 26 | M1, A1, B1 | $4\to1\to5$; complete, inc return to 4; cao |
**Total: [3]**
### Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $4\to1\to5\to(1\to4)\to2\to3\to4$ | B1 | |
**Total: [1]**
### Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting at 1, 2 or 5 gives an HC of length 24. | B1 | |
**Total: [1]**
### Part (v)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 3-arc connector found | M1 | 3-arc connector |
| Value = 15 | A1 | 15 |
| lower bound $= 15 + 2 + 3 = 20$ | B1 | $+2+3$ |
**Total: [3]**
### Part (vi)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Odd vertices are **1, 2, 3, 5** identified | | |
| Pairings: $(1,2)$ and $(3,5)$: $5+9=14$; $(1,3)$ and $(2,5)$: $8+8=16$; $(1,5)$ and $(2,3)$: $3+7=10$ | M1 | must have indication of pairing odd vertices |
| Min length $= 43 + 3 + 7 = 53$ | A1 | cao |
| e.g. route $\mathbf{1\ 5\ 1\ 2\ 3\ 2\ 4\ 3\ 5\ 4\ 1}$ | B1 | cao |
**Total: [3]**
---3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances.\\
\includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}
\begin{enumerate}[label=(\roman*)]
\item The printed answer book shows the initial tables and the results of iterations $1,2,3$ and 5 when Floyd's algorithm is applied to the network.\\
(A) Complete the two tables for iteration 4.\\
(B) Use the final route table to give the shortest route from vertex 5 to vertex 2.\\
(C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
\item Use the nearest neighbour algorithm, starting at vertex $\mathbf { 4 }$, to produce a Hamilton cycle in the complete network. Give the length of your cycle.
\item Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
\item Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
\item Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
\item Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D2 2013 Q3 [20]}}