| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Session | Specimen |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Prim's Algorithm |
| Difficulty | Moderate -0.3 This is a standard application of Prim's algorithm and TSP bounds from a Further Maths Decision module. While it requires multiple steps and understanding of MST/TSP concepts, the procedures are algorithmic and well-rehearsed. The question guides students through each stage explicitly, making it slightly easier than average for A-level but typical for Further Maths Decision content. |
| 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 |
| A | B | C | D | E | |
| A | - | 12 | 8 | 6 | 4 |
| B | 12 | - | 10 | 8 | 10 |
| C | 8 | 10 | - | 13 | 10 |
| D | 6 | 8 | 13 | - | 10 |
| E | 4 | 10 | 10 | 10 | - |
| A | B | C | D | E | |
| F | 2 | 11 | 9 | 7 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (i) | Travelling salesperson problem |
| [1] | 1.2 | |
| 1 | (ii) | A B C D E |
Total weight (cid:32)26km
| Answer | Marks |
|---|---|
| p | B1 |
| Answer | Marks |
|---|---|
| [4] | 1.1a |
| Answer | Marks |
|---|---|
| 3.3 | n |
| Answer | Marks | Guidance |
|---|---|---|
| Weights need not be shown | (or Kruskal, if it was used) | |
| 1 | (iii) | S |
| Answer | Marks |
|---|---|
| (cid:32)33(km) | M1 |
| Answer | Marks | Guidance |
|---|---|---|
| [2] | 3.4 | |
| 1.1 | Their 26 (from (ii)) (cid:14)2(cid:14)5 | |
| 1 | (iv) | (a) |
| Answer | Marks |
|---|---|
| F-A-E-D-B-C-F (cid:32)2(cid:14)4(cid:14)10(cid:14)8(cid:32)10(cid:14)9(cid:32)43 | M1 |
| Answer | Marks |
|---|---|
| [3] | 3.4 |
| Answer | Marks |
|---|---|
| 1.1 | At least one route F-A-E- |
| Answer | Marks | Guidance |
|---|---|---|
| A | B | C |
| A | - | 12 |
| B | 12 | - |
| C | 8 | 10 |
| D | 6 | 8 |
| E | 4 | 10 |
| 1 | (iv) | (b) |
| Answer | Marks |
|---|---|
| 41(km) | M1 |
| Answer | Marks |
|---|---|
| [2] | 3.4 |
| 2.2a | Calculating the length of at least two of |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (v) | E.g. The information so far says that the best |
| Answer | Marks | Guidance |
|---|---|---|
| so we don’t know. | E1 | |
| [1] | 2.2b | n |
Question 1:
1 | (i) | Travelling salesperson problem | B1
[1] | 1.2
1 | (ii) | A B C D E
A - 12 8 6 4
B 12 - 10 8 10
C 8 10 - 13 10
D 6 8 13 - 10
E 4 10 10 10 -
Using Prim’s algorithm starting at A
AE(cid:32)4
AD(cid:32)6
AC(cid:32)8 (or DB(cid:32)8)
DB(cid:32)8 (or AC(cid:32)8)
Total weight (cid:32)26km
p | B1
M1
A1
B1
e
[4] | 1.1a
1.1
i
1.1
c
3.3 | n
e
Stating that Prim has been used
m
A valid order of building the tree for
their starting point (arcs or vertices with
arcs indicated on matrix)
Valid method seen, leading to 26
Correct (labelled) tree
Weights need not be shown | (or Kruskal, if it was used)
1 | (iii) | S
Weight of MST + two least weight arcs to F
(cid:32)26(cid:14)2(cid:11)AF(cid:12)(cid:14)5(cid:11)EF(cid:12)
(cid:32)33(km) | M1
A1FT
[2] | 3.4
1.1 | Their 26 (from (ii)) (cid:14)2(cid:14)5
1 | (iv) | (a) | F-A-E-B-D-C-F (cid:32)2(cid:14)4(cid:14)10(cid:14)8(cid:14)13(cid:14)9(cid:32)46
F-A-E-C-B-D-F (cid:32)2(cid:14)4(cid:14)10(cid:14)10(cid:14)8(cid:14)7(cid:32)41
F-A-E-D-B-C-F (cid:32)2(cid:14)4(cid:14)10(cid:14)8(cid:32)10(cid:14)9(cid:32)43 | M1
M1
A1
[3] | 3.4
1.1
1.1 | At least one route F-A-E-
At least one correct cycle
All three correct cycles
A | B | C | D | E
A | - | 12 | 8 | 6 | 4
B | 12 | - | 10 | 8 | 10
C | 8 | 10 | - | 13 | 10
D | 6 | 8 | 13 | - | 10
E | 4 | 10 | 10 | 10 | -
1 | (iv) | (b) | F-A-E-B-D-C-F (cid:32)46
F-A-E-C-B-D-F (cid:32)41
F-A-E-D-B-C-F (cid:32)43
The length of Fiona’s route is no more than
41(km) | M1
A1
[2] | 3.4
2.2a | Calculating the length of at least two of
the paths given in part (a).
41 from cycle F-A-E-C-B-D-F
1 | (v) | E.g. The information so far says that the best
route is between 26 and 41 km, but the only
route that we have constructed has length 41,
so we don’t know. | E1
[1] | 2.2b | n
Feor an answer that makes clear the
uncertainty due to the lower bound not
being the length of a cycle that has been
found.1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.
\begin{enumerate}[label=(\roman*)]
\item Which standard network problem does Fiona need to solve?
The shortest distances between clients, in km, are given in the matrix below.
\begin{center}
\begin{tabular}{ l | c | c | c | c | c }
& A & B & C & D & E \\
\hline
A & - & 12 & 8 & 6 & 4 \\
\hline
B & 12 & - & 10 & 8 & 10 \\
\hline
C & 8 & 10 & - & 13 & 10 \\
\hline
D & 6 & 8 & 13 & - & 10 \\
\hline
E & 4 & 10 & 10 & 10 & - \\
\hline
\end{tabular}
\end{center}
\item Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.\\
State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree.
The distance from Fiona's house to each client, in km, is given in the table below.
\begin{center}
\begin{tabular}{ c | c | c | c | c | c }
& A & B & C & D & E \\
\hline
F & 2 & 11 & 9 & 7 & 5 \\
\hline
\end{tabular}
\end{center}
\item Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
\item (a) Find all the cycles that result from using the nearest neighbour method, starting at F .\\
(b) Use these to find an upper bound for the length of Fiona's route.
\item Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete Q1 [13]}}