Apply both algorithms and compare

3. \begin{figure}[h] \end{figure}

1. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 2. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
   (3)
2. Starting at A, use Prim's algorithm to find a minimum spanning tree for the network in Figure 2. You must clearly state the order in which you include the arcs in your tree.
   (3)
3. Draw a minimum spanning tree for the network in Figure 2 using the vertices given in Diagram 1 of the answer book. State the weight of the minimum spanning tree.
   (2) A new spanning tree is required which includes the arcs DI and HG, and which has the lowest possible total weight.
4. Explain which algorithm you would choose to complete the tree, and how the algorithm should be adapted. (You do not need to find the tree.)

1. \begin{figure}[h] \end{figure} Figure 1 represents the distances, in km, between eight vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H in a network.

1. 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 your minimum spanning tree.
   (3)
2. Starting at A, use Prim's algorithm to find the minimum spanning tree. You must clearly state the order in which you selected the arcs of your tree.
   (3)
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
4. State the weight of the tree.
   (1)

3. \begin{figure}[h] \end{figure} Figure 1 represents the distance, in metres, between eight data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G and H . The data collection points are to be linked by cables.

1. Listing the arcs in the order that you select them, find a minimum spanning tree for the network using
   1. Kruskal's algorithm, stating in addition any arcs you reject,
   2. Prim's algorithm, starting from A .
2. State the minimum amount of cable needed.
3. Draw your minimum spanning tree using the vertices given in Figure 1 in your answer book.

The matrix represents a network of roads between six villages \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\). The value in each cell represents the distance, in km, along these roads.

1. Show this information on the diagram in the answer book. [2]
2. Use Kruskal's algorithm to determine the minimum spanning tree. State the order in which you include the arcs and the length of the minimum spanning tree. Draw the minimum spanning tree. [5]
3. Starting at \(D\), use Prim's algorithm on the matrix given in the answer book to find the minimum spanning tree. State the order in which you include the arcs. [3]

1. Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network.

\includegraphics{figure_2}

1. Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
   1. Prim's algorithm,
   2. Kruskal's algorithm.
   [4]

\includegraphics{figure_1} Figure 1 represents the distances, in metres, between eight vertices, A, B, C, D, E, F, G and H, in a network.

1. Use Kruskal's algorithm to find a 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 your minimum spanning tree. [3]
2. Complete Matrix 1 in your answer book, to represent the network. [2]
3. Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs. [3]
4. State the weight of the minimum spanning tree. [1]

(Total 9 marks)