1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements.
Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road.
The table below shows the features of each of the six rooms available.
| Room | Floor | Can be seen from road | Looks out onto garden | Has balcony |
| 1 | Ground | ✓ | | |
| 2 | Ground | | ✓ | |
| 3 | First | | ✓ | ✓ |
| 4 | First | ✓ | | ✓ |
| 5 | Second | | ✓ | ✓ |
| 6 | Second | ✓ | | |
- Draw a bipartite graph to show the possible pairings between the stars ( \(A , B , C , D , E\) and \(F\) ) and the rooms ( \(1,2,3,4,5\) and 6 ).
Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
- Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
- Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room.
When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.
| \multirow{2}{*}{} | Room |
| 1 | 2 | 3 | 4 | 5 | 6 |
| Arnie (A) | 3 | 6 | 4 | 1 | 5 | 2 |
| Brigitte ( \(B\) ) | 5 | 3 | 2 | 4 | 1 | 6 |
| Charles (C) | 2 | 1 | 3 | 4 | 5 | 6 |
| Diana (D) | 5 | 4 | 1 | 3 | 2 | 6 |
| Edward ( \(E\) ) | 5 | 6 | 4 | 3 | 2 | 1 |
| Faye (F) | 5 | 6 | 4 | 1 | 3 | 2 |
- Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.