3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_591_1365_239_360}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 2 shows a graph G.
- Write down an example of a cycle on G.
(1) - State, with a reason, whether or not \(\mathrm { P } - \mathrm { Q } - \mathrm { R } - \mathrm { T } - \mathrm { Q } - \mathrm { S }\) is an example of a path on G .
(2)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_618_1406_1336_340}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
The numbers on the \(14 \operatorname { arcs }\) in Figure 3 represent the distances, in km , between eight vertices, \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T } , \mathrm { U } , \mathrm { V }\) and W , in a network. - Use Prim's algorithm, starting at P , to find the minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
- Use Kruskal's algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to the minimum spanning tree.
- Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
The weight on arc RU is now increased to a value of \(x\). The minimum spanning tree for the network is still unique and includes the same arcs as those found in (e).
- Write down the smallest interval that must contain \(x\).