7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.
- On Figure 1 below, use Prim's algorithm, starting from \(P\), to find a minimum spanning tree for the graph connecting \(P , Q , R , S , T\) and \(U\). State clearly the order in which you select the vertices and draw your minimum spanning tree.
\section*{Question 7 continues on page 20}
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
| \(\boldsymbol { P }\) | \(\boldsymbol { Q }\) | \(\boldsymbol { R }\) | \(\boldsymbol { S }\) | \(\boldsymbol { T }\) | \(\boldsymbol { U }\) |
| \(\boldsymbol { P }\) | - | 14 | 7 | 11 | 6 | 12 |
| \(\boldsymbol { Q }\) | 14 | - | 8 | 10 | 9 | 10 |
| \(\boldsymbol { R }\) | 7 | 8 | - | 12 | 13 | 15 |
| \(\boldsymbol { S }\) | 11 | 10 | 12 | - | 5 | 11 |
| \(\boldsymbol { T }\) | 6 | 9 | 13 | 5 | - | 10 |
| \(\boldsymbol { U }\) | 12 | 10 | 15 | 11 | 10 | - |
- Another station, \(V\), is opened. The minimum costs (in euros) of travelling to and from \(V\) to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii).
Arjen is on holiday and he plans to visit each station. He intends to board a train at \(V\) and visit all the other stations, once only, before returning to \(V\).
- By first removing \(V\), obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
- Use the nearest neighbour algorithm twice, starting each time from \(V\), to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)
- Hence find an optimal tour of the seven stations. Explain how you know that it is optimal.
Answer space for question 7(b)
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2(ii)}
| \(\boldsymbol { P }\) | \(Q\) | \(\boldsymbol { R }\) | \(\boldsymbol { S }\) | \(T\) | \(\boldsymbol { U }\) | \(V\) |
| \(\boldsymbol { P }\) | - | 14 | 7 | 11 | 6 | 12 | 15 |
| \(Q\) | 14 | - | 8 | 10 | 9 | 10 | 18 |
| \(\boldsymbol { R }\) | 7 | 8 | - | 12 | 13 | 15 | 14 |
| \(\boldsymbol { S }\) | 11 | 10 | 12 | - | 5 | 11 | 14 |
| \(T\) | 6 | 9 | 13 | 5 | - | 10 | 17 |
| \(\boldsymbol { U }\) | 12 | 10 | 15 | 11 | 10 | - | 12 |
| \(V\) | 15 | 18 | 14 | 14 | 17 | 12 | - |