Easy -1.2 This is a standard bipartite matching problem requiring application of the maximum matching algorithm (likely Hungarian algorithm or inspection method). It's a routine D1 question with clear setup and algorithmic procedure, requiring less mathematical sophistication than typical pure maths questions. The mechanical nature and structured approach make it easier than average A-level content.
1 Alfred has bought six different chocolate bars. He wants to give a chocolate bar to each of his six friends. The table gives the names of the friends and indicates which of Alfred's six chocolate bars they like.
(a) Bipartite graph; 2 sets of 6 labelled (condone errors) vertices; at least 10 edges
M1
All correct, including labelling
A1
2 marks total
(b) \(I - M + G\) or \(C - F + N\) (Allow different notations e.g. those below on the left)
M1
Correct path e.g. \(I - M + G - L + H - O + K - P + J - N + F - C\) or \(I - M + G - L + H - O + K - P + J - N + F - C\) or \(IMGLHOKPJNFC\)
A1
Match FC, GL, HO, IM, JN, KP
B1
3 marks total
**(a)** Bipartite graph; 2 sets of 6 labelled (condone errors) vertices; at least 10 edges | M1 |
All correct, including labelling | A1 | 2 marks total
**(b)** $I - M + G$ or $C - F + N$ (Allow different notations e.g. those below on the left) | M1 |
Correct path e.g. $I - M + G - L + H - O + K - P + J - N + F - C$ or $I - M + G - L + H - O + K - P + J - N + F - C$ or $IMGLHOKPJNFC$ | A1 |
Match FC, GL, HO, IM, JN, KP | B1 | 3 marks total | oe; Must be a list
---
1 Alfred has bought six different chocolate bars. He wants to give a chocolate bar to each of his six friends. The table gives the names of the friends and indicates which of Alfred's six chocolate bars they like.
\hfill \mbox{\textit{AQA D1 2016 Q1 [5]}}