3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a2a6e659-aab5-4eec-9af4-ca6ab895f1c8-04_720_1470_233_296}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
[The weight of the network is \(5 x + 246\) ]
- Explain why it is not possible to draw a graph with an odd number of vertices of odd valency.
Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
Prim's algorithm, starting at A, is applied to the network. The order in which the arcs are selected is \(\mathrm { AD } , \mathrm { DH } , \mathrm { DG } , \mathrm { FG } , \mathrm { EF } , \mathrm { CG } , \mathrm { BD }\). It is given that the order in which the arcs are selected is unique.
- Using this information, find the smallest possible range of values for \(x\), showing your working clearly.
A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex.
Given that the time taken to traverse this route is 318 minutes,
- use an appropriate algorithm to determine the value of \(x\), showing your working clearly.