| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Algorithm Order and Complexity |
| Difficulty | Moderate -0.8 This is a straightforward application of the Chinese Postman Problem to find Eulerian paths in networks. Students need to identify odd-degree vertices, pair them optimally, and add repeated edges—a standard D1 algorithm requiring methodical execution rather than insight. The multi-part structure and calculation steps are typical for this module, but the technique is well-practiced and mechanical. |
| Spec | 7.02h Hamiltonian paths: and cycles7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | odd vertices are \(C\) and \(E\); shortest \(CE = 28\); lowest total = sum of all arcs + shortest \(CE = 218 + 28 = 246\) | B1, M1, M1, A1 |
| (b) | odd vertices are \(C, E, P\) and \(Q\); shortest \(CE\) and \(PQ\) = \(13 + 18 = 31\); \(CP\) and \(EQ\) = \(33 + 28 = 61\); \(CQ\) and \(EP\) = \(15 + 20 = 35\); \(\therefore\) lowest is 31; total = sum of all arcs + 31 = \(213 + 31 = 244\) | B1, M2 A1, M1 A1 |
| (c) | Logo 2 requires 2 cm less stitching | B1 |
**(a)** | odd vertices are $C$ and $E$; shortest $CE = 28$; lowest total = sum of all arcs + shortest $CE = 218 + 28 = 246$ | B1, M1, M1, A1 | |
**(b)** | odd vertices are $C, E, P$ and $Q$; shortest $CE$ and $PQ$ = $13 + 18 = 31$; $CP$ and $EQ$ = $33 + 28 = 61$; $CQ$ and $EP$ = $15 + 20 = 35$; $\therefore$ lowest is 31; total = sum of all arcs + 31 = $213 + 31 = 244$ | B1, M2 A1, M1 A1 | |
**(c)** | Logo 2 requires 2 cm less stitching | B1 | (11) |5. A clothes manufacturer has a trademark "VE" which it wants to embroider on all its garments. The stitching must be done continuously but stitching along the same line twice is allowed.
Logo 1:\\
\includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_524_1338_495_296}
Logo 2:
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_531_1342_1155_299}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{center}
\end{figure}
The weighted networks in Figure 4 represent two possible Logos.\\
The weights denote lengths in millimetres.
\begin{enumerate}[label=(\alph*)]
\item Calculate the shortest length of stitch required to embroider Logo 1 .
\item Calculate the shortest length of stitch required to embroider Logo 2.
\item Hence, determine the difference in the length of stitching required for the two Logos.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q5 [11]}}