1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.
- Arthur wants to use lavender, orange or tangerine.
- Bridget wants to use lavender, mauve or pink.
- Carlos wants to use pink or scarlet.
- Davinder wants to use mauve or pink.
- Eric wants to use lavender or orange.
- Ffion wants to use mauve.
Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.
- Draw a bipartite graph on the insert, showing which neighbours ( \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
- By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
- Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)