| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a straightforward Decision Maths question testing basic graph theory definitions and routine application of Prim's algorithm. Parts (a), (c), and (e) require simple recall of formulas (spanning tree has n-1 arcs, complete graph has n(n-1)/2 arcs). Part (b) tests understanding that a path cannot have more vertices than the graph. Part (d) is a standard textbook application of Prim's algorithm with no complications. All parts are mechanical with no problem-solving or insight required. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 7 | B1 | CAO – choice of answers scores B0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| By definition a path cannot contain a vertex more than once | B1 | Must explicitly state a vertex cannot appear more than once |
| As G contains only 8 vertices, a path on G cannot contain 10 vertices | B1 | As minimum compares 8 with 10; B0 for '10 is too many' without referencing 8 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 11 | B1 | CAO – choice of answers scores B0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Prim's starting at C: CE, CD, CH; EJ, BC; AB, EF | M1 A1 A1 | M1: first three arcs correctly chosen in order (CE, CD, CH) or first four nodes correctly chosen (C, E, D, H). If any explicit rejections seen at any point then M1 (max) only. Accept CD for DC throughout |
| A1: first five arcs in order (CE, CD, CH, EJ, BC) or all eight nodes in order (C, E, D, H, J, B, A, F) | ||
| A1 (CSO): all arcs correctly stated and chosen in correct order | ||
| Misread: Starting at node other than C | M1 only | Must have first three arcs (or four nodes) correct and in correct order |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Weight of MST \(= 177\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| K N V D \(\boxed{H}\) L E S J — Pivot H | M1 | |
| \(\boxed{D}\) E \(\boxed{H}\) K N \(\boxed{V}\) L S J — Pivots D and V | A1 | |
| \(\boxed{D}\) E \(\boxed{H}\) K N \(\boxed{L}\) S J \(\boxed{V}\) — Pivots E and L | ||
| \(\boxed{D}\) E \(\boxed{H}\) \(\boxed{K}\) J \(\boxed{L}\) \(\boxed{N}\) S \(\boxed{V}\) — Pivots K and N | A1ft | |
| D E H J K L N S V — Sort complete + named correctly | A1 (cso) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| K N V D H L E S J | ||
| K N D H L E S J V — V at end, consistent direction | M1 | |
| K D H L E N J S V — 1st and 2nd passes | A1 | |
| D H K E L J N S V | ||
| D H E K J L N S V — 3rd and 4th passes | A1ft | |
| D E H J K L N S V — Sort complete + named correctly | A1 (cso) | b1M1: consistent direction, end number in place; b1A1: first and second passes correct; b2A1ft: third and fourth passes correct following from candidate's second pass; b3A1: CSO including 'sort complete' statement or final list rewritten/sixth pass + named correctly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| K N V D H L E S J | ||
| D K N V E H L J S — D in place, consistent direction | M1 | |
| D E K N V H J L S — 1st and 2nd passes correct | A1 | |
| D E H K N V J L S | ||
| D E H J K N V L S — 3rd and 4th passes | A1ft | |
| D E H J K L N V S | ||
| D E H J K L N S V — Sort complete + named correctly | A1 (cso) |
# Question 3:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| 7 | B1 | CAO – choice of answers scores B0 |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| By definition a path cannot contain a vertex more than once | B1 | Must explicitly state a vertex cannot appear more than once |
| As G contains only 8 vertices, a path on G cannot contain 10 vertices | B1 | As minimum compares 8 with 10; B0 for '10 is too many' without referencing 8 |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| 11 | B1 | CAO – choice of answers scores B0 |
## Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| Prim's starting at C: CE, CD, CH; EJ, BC; AB, EF | M1 A1 A1 | M1: first three arcs correctly chosen in order (CE, CD, CH) or first four nodes correctly chosen (C, E, D, H). If any explicit rejections seen at any point then M1 (max) only. Accept CD for DC throughout |
| | | A1: first five arcs in order (CE, CD, CH, EJ, BC) or all eight nodes in order (C, E, D, H, J, B, A, F) |
| | | A1 (CSO): all arcs correctly stated and chosen in correct order |
| Misread: Starting at node other than C | M1 only | Must have first three arcs (or four nodes) correct and in correct order |
## Part (e):
| Answer | Mark | Guidance |
|--------|------|----------|
| Weight of MST $= 177$ | B1 | CAO |
---
# Question (Sorting – Quick sort middle left / Bubble sort):
## Quick sort middle left:
| Answer | Mark | Guidance |
|--------|------|----------|
| K N V D $\boxed{H}$ L E S J — Pivot H | M1 | |
| $\boxed{D}$ E $\boxed{H}$ K N $\boxed{V}$ L S J — Pivots D and V | A1 | |
| $\boxed{D}$ E $\boxed{H}$ K N $\boxed{L}$ S J $\boxed{V}$ — Pivots E and L | | |
| $\boxed{D}$ E $\boxed{H}$ $\boxed{K}$ J $\boxed{L}$ $\boxed{N}$ S $\boxed{V}$ — Pivots K and N | A1ft | |
| D E H J K L N S V — Sort complete + named correctly | A1 (cso) | |
## Bubble sort left to right:
| Answer | Mark | Guidance |
|--------|------|----------|
| K N V D H L E S J | | |
| K N D H L E S J V — V at end, consistent direction | M1 | |
| K D H L E N J S V — 1st and 2nd passes | A1 | |
| D H K E L J N S V | | |
| D H E K J L N S V — 3rd and 4th passes | A1ft | |
| D E H J K L N S V — Sort complete + named correctly | A1 (cso) | b1M1: consistent direction, end number in place; b1A1: first and second passes correct; b2A1ft: third and fourth passes correct following from candidate's second pass; b3A1: CSO including 'sort complete' statement or final list rewritten/sixth pass + **named correctly** |
## Bubble sort right to left:
| Answer | Mark | Guidance |
|--------|------|----------|
| K N V D H L E S J | | |
| D K N V E H L J S — D in place, consistent direction | M1 | |
| D E K N V H J L S — 1st and 2nd passes correct | A1 | |
| D E H K N V J L S | | |
| D E H J K N V L S — 3rd and 4th passes | A1ft | |
| D E H J K L N V S | | |
| D E H J K L N S V — Sort complete + named correctly | A1 (cso) | |
**Sorting into reverse alphabetical order is acceptable for full marks**3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_595_1269_207_397}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 shows a graph G that contains $17 \operatorname { arcs }$ and 8 vertices.
\begin{enumerate}[label=(\alph*)]
\item State how many arcs there are in a spanning tree for G .\\
(1)
\item Explain why a path on G cannot contain 10 vertices.\\
(2)
\item Determine the number of arcs that would need to be added to G to make G a complete graph with 8 vertices.\\
(1)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_684_1326_1420_370}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 shows a weighted graph.
\item Use Prim's algorithm, starting at C , to find the minimum spanning tree for the weighted graph. You must clearly state the order in which you select the arcs of the tree.\\
(3)
\item State the weight of the minimum spanning tree.\\
(1)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q3 [8]}}