| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with MST |
| Difficulty | Standard +0.3 This is a standard D1 question testing routine application of Dijkstra's algorithm and Prim's algorithm with small networks (6 nodes). Part (b)(iii) requires explaining why the reverse-delete algorithm works, which needs some insight but is accessible. Part (b)(iv) involves simple algebraic manipulation of n(n-1)/2 - (n-1). Overall, this is slightly easier than average as it's mostly algorithmic execution with one conceptual part that's well within D1 scope. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | 3 | 2 | 7 | 8 | 3 | |
| B | 3 | 4 | 5 | |||
| C | 2 | 4 | 6 | |||
| D | 7 | 5 | ||||
| E | 8 | 6 | 2 | |||
| F | 3 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly at E | B1 | Dijkstra — award only if correct at E |
| Other working values correct | B1 | other working values |
| Order of labelling correct | B1 | order of labelling |
| Labels correct | B1 | labels |
| Routes: AB 3, AC 2, AD 7, AFE 5, AF 3 | B1 | routes |
| Lengths correct | B1 | lengths |
| [6] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Tree or attempt at Prim's algorithm | M1 | tree or attempt at Prim |
| Correct minimum spanning tree (edges AB=3, AC=2, BC=5, FE=2, AF=3) with Length \(= 15\) | A1 | |
| Length \(= 15\) | B1 | |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Removes AE, AD, CE then BC | M1 | AE, AD, CE (in order) |
| BC only | A1 | BC only |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| It will remain connected. | B1 | |
| There will be no cycles left. | B1 | |
| Removing a largest possible arc at each stage guarantees a minimum spanning tree. | B1 | |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\frac{n^2-3n+2}{2}\) (or equivalent) arcs for Jill to remove. | B1 | algebraic simplification not needed |
| More than Prim if \(n\) is 5 or more | B1 | |
| [2] |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly at E | B1 | Dijkstra — award only if correct at E |
| Other working values correct | B1 | other working values |
| Order of labelling correct | B1 | order of labelling |
| Labels correct | B1 | labels |
| Routes: AB 3, AC 2, AD 7, AFE 5, AF 3 | B1 | routes |
| Lengths correct | B1 | lengths |
| **[6]** | | |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Tree or attempt at Prim's algorithm | M1 | tree or attempt at Prim |
| Correct minimum spanning tree (edges AB=3, AC=2, BC=5, FE=2, AF=3) with Length $= 15$ | A1 | |
| Length $= 15$ | B1 | |
| **[3]** | | |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Removes AE, AD, CE then BC | M1 | AE, AD, CE (in order) |
| BC only | A1 | BC only |
| **[2]** | | |
## Part (b)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| It will remain connected. | B1 | |
| There will be no cycles left. | B1 | |
| Removing a largest possible arc at each stage guarantees a minimum spanning tree. | B1 | |
| **[3]** | | |
## Part (b)(iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\frac{n^2-3n+2}{2}$ (or equivalent) arcs for Jill to remove. | B1 | algebraic simplification not needed |
| More than Prim if $n$ is 5 or more | B1 | |
| **[2]** | | |4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & & 3 & 2 & 7 & 8 & 3 \\
\hline
B & 3 & & 4 & 5 & & \\
\hline
C & 2 & 4 & & & 6 & \\
\hline
D & 7 & 5 & & & & \\
\hline
E & 8 & & 6 & & & 2 \\
\hline
F & 3 & & & & 2 & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
\item Jack wants to find a minimum spanning tree for the network.
\begin{enumerate}[label=(\roman*)]
\item Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length.
Jill suggests the following algorithm is easier.\\
Step 1 Remove an arc of longest length which does not disconnect the network\\
Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1\\
Step 3 Stop
\item Show the order in which arcs are removed when Jill's algorithm is applied to the network.
\item Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
\item In a complete network on $n$ vertices there are $\frac { n ( n - 1 ) } { 2 }$ arcs. There are $n - 1$ arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm?
For what values of $n$ does Jill have more arcs to remove than Prim has to include?
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2015 Q4 [16]}}