| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2020 |
| Session | November |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Network and route modeling |
| Difficulty | Moderate -0.3 This is a straightforward application of basic graph theory definitions and Prim's algorithm. Part (a) tests recall of standard terminology (walk/trail/path), part (b) is a routine MST algorithm application, and part (c) requires simple comparison of edge weights. All parts are standard textbook exercises with no novel problem-solving required. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | H | |
| A | - | 3 | - | 8 | - | - | \(x\) | - |
| B | 3 | - | 5 | - | - | - | - | - |
| C | - | 5 | - | 4 | 3 | - | - | - |
| D | 8 | - | 4 | - | 5 | - | - | 9 |
| E | - | - | 3 | 5 | - | 7 | 6 | - |
| F | - | - | - | - | 7 | - | - | - |
| G | \(x\) | - | - | - | 6 | - | - | 2 |
| H | - | - | - | 9 | - | - | 2 | - |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (a) | (i) |
| Answer | Marks |
|---|---|
| e.g. A – D – E – D – H | B1 |
| [1] | A walk from A to H that repeats an arc (or arcs) |
| (ii) | e.g. A – D – C – E – D – H |
| e.g. A – B – C – D – A – G – H | B1 |
| [1] | A trail from A to H (does not repeat any arcs) that does |
| Answer | Marks | Guidance |
|---|---|---|
| (iii) | e.g. A – D – H | |
| e.g. A – B – C – D – E – G – H | B1 | |
| [1] | A path from A to H (does not repeat any nodes) | |
| 3 | (b) | AB = 3 |
| Answer | Marks |
|---|---|
| EF = 7 | B1 |
| Answer | Marks |
|---|---|
| [3] | For reference |
| Answer | Marks | Guidance |
|---|---|---|
| (c) | (i) | {x: 0 ≤ x ≤ 6} |
| [1] | x ≤ 6, x ≤ (their largest weight used to A or G) |
| Answer | Marks | Guidance |
|---|---|---|
| (ii) | EG | B1 |
| [1] | Follow through their spanning tree from (b) |
Question 3:
3 | (a) | (i) | e.g. A – B – A – D – H
e.g. A – B – C – D – E – C – D – H
e.g. A – D – E – D – H | B1
[1] | A walk from A to H that repeats an arc (or arcs)
(ii) | e.g. A – D – C – E – D – H
e.g. A – B – C – D – A – G – H | B1
[1] | A trail from A to H (does not repeat any arcs) that does
repeat a node (or nodes)
(iii) | e.g. A – D – H
e.g. A – B – C – D – E – G – H | B1
[1] | A path from A to H (does not repeat any nodes)
3 | (b) | AB = 3
BC = 5
CE = 3
CD = 4
EG = 6
GH = 2
EF = 7 | B1
M1
A1
[3] | For reference
Choosing the 7 circled entries, shown on table
Must be on the table and all correct (not any transposes)
A spanning tree for the 8 nodes
need not match the arcs in the network, need not be MST
Correct tree drawn or correct arcs listed (not just on table)
(c) | (i) | {x: 0 ≤ x ≤ 6} | B1
[1] | x ≤ 6, x ≤ (their largest weight used to A or G)
Allow strict inequality
(ii) | EG | B1
[1] | Follow through their spanning tree from (b)3\\
\includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-4_399_1331_255_367}
\begin{enumerate}[label=(\alph*)]
\item By listing the vertices passed through, in the order they are used, give an example for the graph above of:
\begin{enumerate}[label=(\roman*)]
\item a walk from A to H that is not a trail,
\item a trail from A to H that is not a path,
\item a path from A to H that is not a cycle.
The arcs are weighted to form a network. The arc weights are shown in the table, apart from the weight of arc AG. The arcs model a system of roads and the weights represent distances in km.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G & H \\
\hline
A & - & 3 & - & 8 & - & - & $x$ & - \\
\hline
B & 3 & - & 5 & - & - & - & - & - \\
\hline
C & - & 5 & - & 4 & 3 & - & - & - \\
\hline
D & 8 & - & 4 & - & 5 & - & - & 9 \\
\hline
E & - & - & 3 & 5 & - & 7 & 6 & - \\
\hline
F & - & - & - & - & 7 & - & - & - \\
\hline
G & $x$ & - & - & - & 6 & - & - & 2 \\
\hline
H & - & - & - & 9 & - & - & 2 & - \\
\hline
\end{tabular}
\end{center}
The road modelled by arc AG is temporarily closed.
\end{enumerate}\item Use the matrix form of Prim's algorithm to find a minimum spanning tree, of total weight 30 km , that does not include arc AG.
The road modelled by arc AG is now reopened.
\item \begin{enumerate}[label=(\roman*)]
\item For what set of values of $x$ could AG be included in a minimum spanning tree for the full network?
\item Which arc from the minimum spanning tree in part (b) is not used when arc AG is included?
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2020 Q3 [8]}}