Define tree terminology

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

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the minimum spanning tree.

2. Prim's algorithm finds a minimum spanning tree for a connected graph.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Name an alternative algorithm for finding a minimum spanning tree. \begin{table}[h]

   	Cambridge	London	Norwich	Oxford	Portsmouth	Salisbury	York
   Cambridge (C)	-	60	62	81	132	139	156
   London (L)	60	-	116	56	74	88	211
   Norwich (N)	62	116	-	144	204	201	181
   Oxford (O)	81	56	144	-	84	63	184
   Portsmouth (P)	132	74	204	84	-	43	269
   Salisbury (S)	139	88	201	63	43	-	248
   York (Y)	156	211	181	184	269	248	-

   \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{table} Figure 2 shows the distances by road, in miles, between seven cities.
3. 1. Use Prim's algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.
   2. Draw your tree using the vertices given in Diagram 2 in the answer book.
      (5)

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

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.

6. (a) Define the terms

1. tree,
2. spanning tree,
3. minimum spanning tree.
   (3)
   (b) State one difference between Kruskal's algorithm and Prim's algorithm, to find a minimum spanning tree.
   (1) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-08_894_1529_920_322}
   \end{figure} (c) Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Fig. 4. State the order in which you included the arcs. Draw the minimum spanning tree in Diagram 1 in the answer book and state its length.
   (4) \section*{Figure 5}
   \includegraphics[max width=\textwidth, alt={}]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-09_887_1536_342_258}
   Figure 5 models a car park. Currently there are two pay-stations, one at \(E\) and one at \(N\). These two are linked by a cable as shown. New pay-stations are to be installed at \(B , H , A , F\) and \(C\). The number on each arc represents the distance between the pay-stations in metres. All of the pay-stations need to be connected by cables, either directly or indirectly. The current cable between \(E\) and \(N\) must be included in the final network. The minimum amount of new cable is to be used.
   (d) Using your answer to part (c), or otherwise, determine the minimum amount of new cable needed. Use Diagram 2 to show where these cables should be installed. State the minimum amount of new cable needed.
   (3)

1 Answer this question on the insert provided. The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components. \begin{figure}[h] \end{figure} The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.

1. Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number. The electrician has a junction box. This can be represented by an eighth node on the graph.
2. What is the minimum number of connections which the electrician will have to make if he uses the junction box?
3. The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway? The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.
4. Will this result in the minimum number of connections? Justify your answer.

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\ \text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\ & \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\ & \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\ & \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

1. Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables \(\mathrm { AB } , \mathrm { AC } , \ldots\) correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
2. Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
3. Explain what is ensured by the constraint \(\mathrm { AB } + \mathrm { AC } \geqslant 1\). Julie claims that the solution to the problem will give the minimum spanning tree for the network.
4. Find the minimum spanning tree for the network.
   Kim has a different network, exactly one of the arcs in this network is a directed arc.
   Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
5. Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
   \hfill [3]
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. \hfill [1]

The table below shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.

1. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights. \hfill [2]
2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. \hfill [3]
3. State the weight of the minimum spanning tree. \hfill [1]