6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-07_608_1468_194_296}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
[The weight of the network is \(20 x + 17\) ]
- Explain why it is not possible to draw a network with an odd number of vertices of odd valency.
Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
- During rush hour one day \(x = 9\)
- Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
- Calculate the weight of the minimum spanning tree.
You are now given that \(x > 3\)
A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex.
The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
- Determine the value of \(x\), showing your working clearly.