| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | January |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a routine application of a standard D1 algorithm with minimal problem-solving required. Part (a) is pure recall of a definition, and part (b) involves mechanically applying the maximum matching algorithm to a given bipartite graph with an initial matching already provided. The question guides students through each step and requires no novel insight or complex reasoning. |
| Spec | 7.02j Isomorphism: of graphs, degree sequences7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A bipartite graph consists of two sets of vertices X and Y | B1 | Must contain the three words: "two", "sets", "vertices" – accept "nodes" for vertices but not "points" or non-technical language |
| The edges only join vertices in X to vertices in Y, not vertices within a set | B1 | Edges/arcs must go from one set into the other. Candidates must use either "arc(s)" or "edge(s)". If candidate only says cannot connect nodes from same set: B0. Minimum accept: "edges must go from one to the other" |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path: \(D - 6 = E - 5 = F - 4 = B - 3\) | M1 | An alternating path from D to 3 (or vice versa) |
| Change status: \(D = 6,\ E = 5,\ F = 4,\ B = 3\) | A1 | CAO – a correct path including change status either stated or shown. Chosen path must be clear. No isw. |
| Complete matching: \(A = 1,\ B = 3,\ C = 2,\ D = 6,\ E = 5,\ F = 4\) | A1 | CAO – must follow from the correct stated path. Accept on a clear diagram (with six arcs only) |
**Question 1:**
**Part (a):**
| Answer | Mark | Guidance |
|--------|------|----------|
| A bipartite graph consists of two sets of vertices X and Y | B1 | Must contain the three words: "two", "sets", "vertices" – accept "nodes" for vertices but not "points" or non-technical language |
| The edges only join vertices in X to vertices in Y, not vertices within a set | B1 | Edges/arcs must go from one set into the other. Candidates must use either "arc(s)" or "edge(s)". If candidate only says cannot connect nodes from same set: B0. Minimum accept: "edges must go from one to the other" |
**Part (b):**
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path: $D - 6 = E - 5 = F - 4 = B - 3$ | M1 | An alternating path from D to 3 (or vice versa) |
| Change status: $D = 6,\ E = 5,\ F = 4,\ B = 3$ | A1 | CAO – a correct path including change status **either** stated **or** shown. Chosen path must be clear. No isw. |
| Complete matching: $A = 1,\ B = 3,\ C = 2,\ D = 6,\ E = 5,\ F = 4$ | A1 | CAO – must follow from the correct stated path. Accept on a clear diagram (with six arcs only) |
**Total: 5 marks**1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-02_611_515_333_397}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-02_611_515_333_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Define the term 'bipartite graph'.
Figure 1 shows the possible allocations of six people, A , B , C , D , E and F , to six activities, $1,2,3$, 4, 5 and 6
Figure 2 shows an initial matching.
\item Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q1 [5]}}