2 A document which is currently written in English is to be translated into six other European Union languages. The cost of translating a document varies, as it is harder to find translators for some languages.
The costs, in euros, are shown in the table below.
- On the table below, showing the order in which you select the edges, use Prim's algorithm, starting from \(E\), to find a minimum spanning tree for the graph connecting \(D , E , F , G , H , I\) and \(S\).
- Find the length of your minimum spanning tree.
- Draw your minimum spanning tree.
- It is given that the graph has a unique minimum spanning tree.
State the final two edges that would be added to complete the minimum spanning tree in the case where:
- Prim's algorithm starting from \(H\) is used;
- Kruskal's algorithm is used.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Answer space for question 2}
| Danish ( \(\boldsymbol { D }\) ) | English ( \(\boldsymbol { E }\) ) | French (F) | German ( \(G\) ) | Hungarian (H) | Italian (I) | Spanish \(\boldsymbol { ( } \boldsymbol { S } \boldsymbol { ) }\) |
| Danish (D) | - | 120 | 140 | 80 | 170 | 140 | 140 |
| English ( \(\boldsymbol { E }\) ) | 120 | - | 70 | 80 | 130 | 130 | 110 |
| French (F) | 140 | 70 | - | 90 | 190 | 85 | 90 |
| German ( \(G\) ) | 80 | 80 | 90 | - | 110 | 100 | 100 |
| Hungarian (H) | 170 | 130 | 190 | 110 | - | 140 | 150 |
| Italian (I) | 140 | 130 | 85 | 100 | 140 | - | 60 |
| Spanish ( \(\boldsymbol { S }\) ) | 140 | 110 | 90 | 100 | 150 | 60 | - |