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.
| 1 | 2 | 3 | 4 | 5 | 6 |
| A | | | | | \(\checkmark\) | |
| B | \(\checkmark\) | | | \(\checkmark\) | | |
| C | \(\checkmark\) | \(\checkmark\) | | \(\checkmark\) | | |
| D | | | | | \(\checkmark\) | |
| E | | | \(\checkmark\) | | \(\checkmark\) | \(\checkmark\) |
| F | | | | \(\checkmark\) | | |
- 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 - Show this information, in a distinctive way, on the diagram in the answer book.
(1) - Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
- Explain why it is not possible to find a complete matching.