| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2020 |
| Session | November |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Calculate MST length/weight/cost |
| Difficulty | Moderate -0.3 This is a standard MST question using Kruskal's/Prim's algorithm with straightforward application of lower/upper bound algorithms for TSP. Part (a) is routine, parts (b)(i-iii) require systematic but mechanical application of standard algorithms, and part (d) involves basic logical deduction. The question is slightly easier than average because it's purely algorithmic with no novel problem-solving required, though the multiple parts and TSP bounds prevent it from being significantly below average. |
| 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 |
| \(\mathrm { A } , \mathrm { B }\) | \(\mathrm { A } , \mathrm { C }\) | \(\mathrm { A } , \mathrm { D }\) | \(\mathrm { A } , \mathrm { E }\) | \(\mathrm { B } , \mathrm { C }\) | \(\mathrm { B } , \mathrm { D }\) | \(\mathrm { B } , \mathrm { E }\) | \(\mathrm { C } , \mathrm { D }\) | \(\mathrm { C } , \mathrm { E }\) | \(\mathrm { D } , \mathrm { E }\) |
| 300 | 500 | 900 | 700 | 200 | 600 | 400 | 500 | - | 100 |
| Answer | Marks |
|---|---|
| 5 | For reference: |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (a) | D – E – B – C |
| Answer | Marks |
|---|---|
| £1000 | M1 |
| Answer | Marks |
|---|---|
| [2] | Any spanning tree for the 5 vertices |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (b) | (i) |
| Answer | Marks |
|---|---|
| Best lower bound = £1600 | M1 |
| Answer | Marks |
|---|---|
| [4] | Weight of any one of these reduced MST’s seen |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (ii) | Nearest neighbour method |
| Answer | Marks |
|---|---|
| Best upper bound = £1800 | M1 |
| Answer | Marks |
|---|---|
| [4] | Nearest neighbour (even if not closed, but visiting all 5 |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (iii) | A – B – C – D – E – A |
| Answer | Marks |
|---|---|
| [2] | First three vertices correct, for any starting point and direction |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (c) | Need to pave a route from the shop to the first field |
| [1] | Connect to shop, fields are not points, or other valid reason | |
| 5 | (d) | (i) |
| so cost of CE < £300 | M1 |
| Answer | Marks |
|---|---|
| [2] | Shortest route including CE, or implied from cost www |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (d) | (ii) |
| £600 + cost of CE < £900 | M1 |
| Answer | Marks |
|---|---|
| [2] | MST including CE, or implied from cost www |
| Answer | Marks | Guidance |
|---|---|---|
| AB | AC | AD |
Question 5:
5 | For reference:
AB AC AD AE BC BD BE CD CE DE
300 500 900 700 200 600 400 500 - 100
5 | (a) | D – E – B – C
|
A
£1000 | M1
A1
[2] | Any spanning tree for the 5 vertices
May list arcs included rather than drawing tree, oe
1000 (cao)
5 | (b) | (i) | Lower bound for TSP
Deleting A: MST = 700 700 + 300 + 500 = 1500
Deleting B: MST = 1100 1100 + 200 + 300 = 1600
Deleting C: MST = 800 800 + 200 + 500 = 1500
Deleting D: MST = 900 900 + 100 +500 = 1500
Deleting E: MST = 1000 1000 + 100 + 400 = 1500
Best lower bound = £1600 | M1
A1
A1
B1
[4] | Weight of any one of these reduced MST’s seen
A correct calculation of ‘MST + two least weight arcs from
deleted vertex’
Their best (greatest) lower bound (with all 5 totals given)
1600 (cao)
5 | (ii) | Nearest neighbour method
A – B – C – D – E – A = 1800
B – C – D – E – A – B = 1800
C – B – A – E – D – C = 1800
D – E – B – C – A – D = 2100
E – D – C – B – A – E = 1800
Best upper bound = £1800 | M1
A1
A1
B1
[4] | Nearest neighbour (even if not closed, but visiting all 5
vertices) for at least one starting point, or implied from a
correct total
At least three correct totals
Their best (least) upper bound (with all 5 totals given)
1800 (cao)
5 | (iii) | A – B – C – D – E – A | M1
A1FT
[2] | First three vertices correct, for any starting point and direction
Correct cycle, or in reverse, with any starting point
Or FT cycle seen in answer to (b)(ii) if UB ≠ 1800
5 | (c) | Need to pave a route from the shop to the first field | B1
[1] | Connect to shop, fields are not points, or other valid reason
5 | (d) | (i) | A – C – E – D (or A–B–C–E–D) < 900
so cost of CE < £300 | M1
A1
[2] | Shortest route including CE, or implied from cost www
300 (or 299.99, 299, 290)
5 | (d) | (ii) | MST = CE + ED + CB + BA (CE replaces BE)
£600 + cost of CE < £900 | M1
A1FT
[2] | MST including CE, or implied from cost www
900 (or 899.99, 899, 890), follow through their 300 from (d)(i)
AB | AC | AD | AE | BC | BD | BE | CD | CE | DE5 The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E.\\
The table shows the cost, in $\pounds$, of making a paved path between each pair of fields.\\
A river means that it is not possible to make a paved path between C and E .
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | c | }
\hline
$\mathrm { A } , \mathrm { B }$ & $\mathrm { A } , \mathrm { C }$ & $\mathrm { A } , \mathrm { D }$ & $\mathrm { A } , \mathrm { E }$ & $\mathrm { B } , \mathrm { C }$ & $\mathrm { B } , \mathrm { D }$ & $\mathrm { B } , \mathrm { E }$ & $\mathrm { C } , \mathrm { D }$ & $\mathrm { C } , \mathrm { E }$ & $\mathrm { D } , \mathrm { E }$ \\
\hline
300 & 500 & 900 & 700 & 200 & 600 & 400 & 500 & - & 100 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Determine the minimum cost of connecting the fields.
\item \begin{enumerate}[label=(\roman*)]
\item By applying the lower bound algorithm to each vertex in turn, determine a best lower bound for $P$, the minimum cost of making a circular tour (cycle) of paved paths that visits each field once.
\item By applying the nearest neighbour algorithm, starting at each vertex in turn, find a best upper bound for $P$. You do not need to attempt any route improvements.
\item Give the order in which the fields are visited in a circular tour of paved paths that corresponds to the best upper bound found in part (b)(ii).
\end{enumerate}\item Give a practical reason why the total cost of paving for the project might be more than the best upper bound found in part (b)(ii).
It becomes possible to use an existing bridge to make a paved route between C and E . Using this bridge, there is a new indirect route from A to D that costs less than $\pounds 900$ to pave.
\item When this bridge is used, what can be determined about the minimum cost of
\begin{enumerate}[label=(\roman*)]
\item paving the route between C and E
\item connecting all the fields?
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2020 Q5 [17]}}