4 Pam has seven employees. When it snows they all need to be contacted by telephone.
The table shows the expected time, in minutes, that it will take Pam and her employees to contact each other.
| Pam | Alan | Bob | Caz | Dan | Ella | Fred | Gita |
| Pam | - | 10 | 4 | 8 | 18 | 12 | 12 | 9 |
| Alan | 10 | - | 6 | 10 | 18 | 12 | 11 | 9 |
| Bob | 4 | 6 | - | 9 | 17 | 10 | 11 | 10 |
| Caz | 8 | 10 | 9 | - | 15 | 13 | 10 | 7 |
| Dan | 18 | 18 | 17 | 15 | - | 16 | 19 | 20 |
| Ella | 12 | 12 | 10 | 13 | 16 | - | 13 | 14 |
| Fred | 12 | 11 | 11 | 10 | 19 | 13 | - | 18 |
| Gita | 9 | 9 | 10 | 7 | 20 | 14 | 18 | - |
- Use the nearest neighbour method, starting from Pam, to find a cycle through all the employees and Pam. If there is a choice of names choose the one that occurs first alphabetically. Calculate the total weight of this cycle.
- Apply Prim's algorithm to the copy of the table in the answer book, starting by crossing out the row for Pam and looking down the column for Pam. List the arcs in the order in which they were chosen. Draw the resulting minimum spanning tree and calculate its total weight.
- Find a lower bound for the minimum weight cycle through Pam and her seven employees by initially removing Gita from the minimum spanning tree.
Pam realises that it takes less time if she splits the employees into teams.
- Use the minimum spanning tree to suggest how to split the employees into two teams, so that Pam contacts the two team leaders and they each contact the members of their team. Using this solution, find the minimum elapsed time by which all the employees can be contacted.