| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| 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 straightforward application of a standard D1 algorithm with minimal steps. Part (a) is pure recall of a definition, and part (b) requires following the maximum matching algorithm mechanically from a given starting point—no problem-solving insight or complex reasoning needed, just procedural execution of a taught method. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | 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 |
| The edges only join vertices in \(X\) to vertices in \(Y\), not vertices within a set | B1 | Edges must go from one set into the other; candidates must indicate going from one set to the other; no need to use the word "set"; if candidate implies bipartite graph can join vertices within a set, withhold this mark (no isw) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Alternating path: \(P - A = N - E = T - D = L - C = M - B\) | M1 | A correct alternating path from \(P\) to \(B\) or vice versa |
| Change status: \(P = A - N = E - T = D - L = C - M = B\) | A1 | CAO — accept change status either stated (e.g. "change (of) status" or "c.s.") or shown (all symbols interchanged) |
| Complete matching: \(L = C,\ M = B,\ N = E,\ P = A,\ T = D\) | A1 | CAO — must follow from the correct stated path; accept stated or on a clear diagram (five arcs only) |
| Total: 3 marks | Question total: 5 marks |
## Question 1:
### Part (a)
| Answer | Marks | 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 |
| The edges only join vertices in $X$ to vertices in $Y$, not vertices within a set | B1 | Edges must go from one set into the other; candidates must indicate going from one set to the other; no need to use the word "set"; if candidate implies bipartite graph **can** join vertices within a set, withhold this mark (**no isw**) |
**Total: 2 marks**
---
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Alternating path: $P - A = N - E = T - D = L - C = M - B$ | M1 | A correct alternating path from $P$ to $B$ or vice versa |
| Change status: $P = A - N = E - T = D - L = C - M = B$ | A1 | CAO — accept change status either stated (e.g. "change (of) status" or "c.s.") **or** shown (all symbols interchanged) |
| Complete matching: $L = C,\ M = B,\ N = E,\ P = A,\ T = D$ | A1 | CAO — must follow from the correct stated path; accept stated **or** on a **clear** diagram (five arcs **only**) |
**Total: 3 marks | Question total: 5 marks**
---
**Additional guidance for part (b):**
- $P * A = N * E = T * D = L * C = M * B$ then $P = A * N = E * T = D * L = C * M = B$ → scores M1A1 (change status shown)
- Change status $P = A - N = E - T = D - L = C - M = B$ → scores M1A1 (change status stated)
- $P - A = N - E = T - D = L - C = M - B$ then $P = A,\ N = E,\ T = D, \ldots$ → scores M1A0 (no change status stated or shown)1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-02_492_515_374_383}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-02_492_529_379_1160}
\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 five people, Larry (L), Monisha (M), Nina (N), Phil (P) and Theo (T), to five activities, A, B, C, D and E.
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 you use and state your complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q1 [5]}}