| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2021 |
| Session | November |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Network construction from matrix |
| Difficulty | Standard +0.3 This is a straightforward application of standard algorithms (shortest path, MST) to a small network with clearly labeled distances. Part (a) requires simple inspection, part (b) is systematic Floyd-Warshall or inspection, part (c) applies Prim's/Kruskal's to a 6-vertex complete graph, and part (d) requires finding a specific route of given length. All parts are routine algorithmic applications with no novel problem-solving required, making this slightly easier than average. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (a) | ABXE |
| [1] | 1.1 | |
| 3 | (b) | A |
| Answer | Marks |
|---|---|
| 3.3 2.7 2.5 0.6 0.7 F | M1 |
| Answer | Marks |
|---|---|
| [4] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | AB = 0.6, AC = 1.1 |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (c) | AB = 0.6 |
| Answer | Marks |
|---|---|
| 4.8 C E | M1 |
| Answer | Marks |
|---|---|
| [3] | 3.1 b |
| Answer | Marks |
|---|---|
| 1.1 | A graph that connects {A, B, C, D, E, F} |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (d) | Adapting the answer to part (c) |
| B – A – C – X – Y – E – F – D | M1 | |
| A1 | 3.1b | |
| 1.1 | Any walk or cycle that starts at B and uses every vertex at least once, |
| Answer | Marks | Guidance |
|---|---|---|
| 0.6 | B | |
| 1.1 | 1.7 | C |
| 2.7 | 2.1 | 2.5 |
| 2.8 | 2.2 | 1.8 |
| 3.3 | 2.7 | 2.5 |
| Answer | Marks |
|---|---|
| 4 | (a) |
| (a) | (i) |
| (ii) | Points won Mia |
| Answer | Marks |
|---|---|
| Z -5.5 -0.5 3.5 | B1 |
| Answer | Marks |
|---|---|
| B1 | 1.1 |
| 1.1 | 15, 9 and 6 all correct |
| Answer | Marks | Guidance |
|---|---|---|
| Z -11 -1 7 | B1 | Points won by Li minus points won by Mia |
Question 3:
3 | (a) | ABXE | B1
[1] | 1.1
3 | (b) | A
0.6 B
1.1 1.7 C
2.7 2.1 2.5 D
2.8 2.2 1.8 1.2 E
3.3 2.7 2.5 0.6 0.7 F | M1
A1
M1
A1
[4] | 1.1
1.1
1.1
1.1 | AB = 0.6, AC = 1.1
AD = 2.7, AE = 2.8
DF = 0.6, EF = 0.7
BF = 2.7, CF = 2.5
AF = 3.3 or ft from other values
3 | (c) | AB = 0.6
AC = 1.1 B D
CE = 1.8
EF = 0.7 A X Y • F
DF = 0.6
4.8 C E | M1
A1
B1 ft
[3] | 3.1 b
3.2 a
1.1 | A graph that connects {A, B, C, D, E, F}
with or without X and/or Y
Correct tree drawn or arcs listed, including CX and XE
4.8 (km) or total for their tree
3 | (d) | Adapting the answer to part (c)
B – A – C – X – Y – E – F – D | M1
A1 | 3.1b
1.1 | Any walk or cycle that starts at B and uses every vertex at least once,
including X and Y
cao
[2]
A
0.6 | B
1.1 | 1.7 | C
2.7 | 2.1 | 2.5 | D
2.8 | 2.2 | 1.8 | 1.2 | E
3.3 | 2.7 | 2.5 | 0.6 | 0.7 | F
4
4 | (a)
(a) | (i)
(ii) | Points won Mia
by Mia X Y Z
X 4 15 9
Li Y 11 6 5
Z 10 5 1
Points won Mia
by Li X Y Z
X 0.5 -10.5 -4.5
Li Y -6.5 -1.5 -0.5
Z -5.5 -0.5 3.5 | B1
[1]
B1 | 1.1
1.1 | 15, 9 and 6 all correct
Subtract 4.5 from each value in the table showing points won by Li
All correct
Or any positive multiple of this table
Alternative solution
Points won Mia
by Li X Y Z
X 1 -21 -9
Li Y -13 -3 -1
Z -11 -1 7 | B1 | Points won by Li minus points won by Mia
All correct (not follow through from (a))
[1]3 The diagram shows a simplified map of the main streets in a small town.\\
\includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246}
Some of the junctions have traffic lights, these junctions are labelled A to F .\\
There are no traffic lights at junctions X and Y .\\
The numbers show distances, in km, between junctions.
Alex needs to check that the traffic lights at junctions A to F are working correctly.
\begin{enumerate}[label=(\alph*)]
\item Find a route from A to E that has length 2.8 km .
Alex has started to construct a table of shortest distances between junctions A to F.\\
\includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246}
For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
\item Complete the copy of the table in the Printed Answer Booklet.
\item Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
\begin{itemize}
\item Write down the total length of the minimum spanning tree.
\item List which arcs of the original network correspond to the arcs used in your minimum spanning tree.
\end{itemize}
Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
\item Write down the junctions in the order that Beth visited them.
Do not draw on your answer from part (c).
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2021 Q3 [10]}}