| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | November |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a standard textbook application of the maximum matching algorithm (typically Hungarian algorithm or alternating path method) in D1. The bipartite graph is small and straightforward, the alternating path method is algorithmic with clear steps, and part (d) requires only basic application of Hall's Marriage Theorem or observation that two reporters (A and D) can only be assigned to story 5. This is routine recall and application of a standard algorithm with no novel problem-solving required. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| 1 | 2 | 3 | 4 | 5 | 6 | |
| A | \(\checkmark\) | |||||
| B | \(\checkmark\) | \(\checkmark\) | ||||
| C | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | |||
| D | \(\checkmark\) | |||||
| E | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | |||
| F | \(\checkmark\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph drawn with all correct arcs shown (A,B,C,D,E,F matched to 1-6) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Complete matching shown in diagram | B1 | |
| (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(\beta - 1 = C - 2\), c.s. \(\beta = 1 - C = 2\) | M1A1 | |
| \(A=5, B=1, C=2, E=6, F=4\) | B1(c.s.) | |
| A1√ | ||
| (4) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. Both \(A\) and \(D\) are only matched to 5; once one has been assigned the other cannot be. E is the only person who can do 3, and the only person who can do 6; if they are assigned to one of these the other cannot be done. | B2,1,0 | |
| (2) | ||
| [8] |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph drawn with all correct arcs shown (A,B,C,D,E,F matched to 1-6) | B1 | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Complete matching shown in diagram | B1 | |
| | (2) | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $\beta - 1 = C - 2$, c.s. $\beta = 1 - C = 2$ | M1A1 | |
| $A=5, B=1, C=2, E=6, F=4$ | B1(c.s.) | |
| | A1√ | |
| | (4) | |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. Both $A$ and $D$ are only matched to 5; once one has been assigned the other cannot be. E is the only person who can do 3, and the only person who can do 6; if they are assigned to one of these the other cannot be done. | B2,1,0 | |
| | (2) | |
| | **[8]** | |
---3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
A & & & & & $\checkmark$ & \\
\hline
B & $\checkmark$ & & & $\checkmark$ & & \\
\hline
C & $\checkmark$ & $\checkmark$ & & $\checkmark$ & & \\
\hline
D & & & & & $\checkmark$ & \\
\hline
E & & & $\checkmark$ & & $\checkmark$ & $\checkmark$ \\
\hline
F & & & & $\checkmark$ & & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show these possible allocations on the bipartite graph on the diagram in the answer book.
A possible matching is\\
A to 5,\\
C to 1 ,\\
E to 6,\\
F to 4
\item Show this information, in a distinctive way, on the diagram in the answer book.\\
(1)
\item Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
\item Explain why it is not possible to find a complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q3 [8]}}