3 A group of eight friends, \(A , B , C , D , E , F , G\) and \(H\), keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table.
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | \(\boldsymbol { F }\) | \(\boldsymbol { G }\) | \(\boldsymbol { H }\) |
| \(\boldsymbol { A }\) | - | 15 | 10 | 12 | 16 | 11 | 14 | 17 |
| \(\boldsymbol { B }\) | 15 | - | 15 | 14 | 15 | 16 | 16 | 15 |
| \(\boldsymbol { C }\) | 10 | 15 | - | 11 | 10 | 12 | 14 | 9 |
| \(\boldsymbol { D }\) | 12 | 14 | 11 | - | 11 | 12 | 14 | 12 |
| \(\boldsymbol { E }\) | 16 | 15 | 10 | 11 | - | 13 | 15 | 14 |
| \(\boldsymbol { F }\) | 11 | 16 | 12 | 12 | 13 | - | 14 | 8 |
| G | 14 | 16 | 14 | 14 | 15 | 14 | - | 13 |
| \(\boldsymbol { H }\) | 17 | 15 | 9 | 12 | 14 | 8 | 13 | - |
One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.
- Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the table.
- Draw your minimum spanning tree.
- Find the minimum total cost.
- Person \(H\) leaves the group. Find the new minimum total cost.