MST with vertex removed

2 The network below shows 8 towns, \(A , B , \ldots , H\). The number on each edge shows the length of the road, in miles, between towns. During the winter, the council treats some of the roads with salt so that each town can be safely reached on treated roads from any other town. It costs \(\pounds 30\) to treat a mile of road. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-04_876_1611_497_210}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. Draw your minimum spanning tree.
   3. Calculate the minimum cost to the council of making it possible for each town to be safely reached on treated roads from any other town.
2. On one occasion, the road from \(C\) to \(E\) is impassable because of flooding. Find the minimum cost of treating sufficient roads for safe travel in this case.
   [0pt] [2 marks]

The following network shows the lengths, in miles, of roads connecting nine villages, \(A\), \(B\), ..., \(I\). \includegraphics{figure_3}

1. 1. Use Prim's algorithm starting from \(E\), showing the order in which you select the edges, to find a minimum spanning tree for the network. [4]
   2. State the length of your minimum spanning tree. [1]
   3. Draw your minimum spanning tree. [2]
2. On a particular day, village \(B\) is cut off, so its connecting roads cannot be used. Find the length of a minimum spanning tree for the remaining eight villages. [2]

This question should be answered on the sheet provided. \includegraphics{figure_2} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.

1. Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected. [4 marks]
2. It is decided that a Greek translation is not needed. Find the minimum cost if:
   1. translations to and from Greek are not available,
   2. translations to and from Greek are still available. [3 marks]
3. Comment on your findings. [1 mark]

Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.

1. How would you overcome the problem of having different costs for reverse translations? [1 mark]
2. What algorithm would be suitable to find a computerised solution. [1 mark]
3. State another assumption you have made in answering this question and comment on its validity. [2 marks]