7.04b Minimum spanning tree: Prim's and Kruskal's algorithms

3 A mining company wants to open a new mine in an area where the ground contains a precious metal. The mining company has carried out a survey of the area. The network below shows nodes which represent the entrance to the new mine, \(X\), and the 8 ventilation shafts, \(A , B , \ldots , H\), which have been installed to prevent the build up of dangerous gases underground. \includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-04_846_1228_623_404} Each arc represents a possible underground tunnel which could be mined.
The weight on each arc represents the estimated amount of precious metal in that possible underground tunnel in tonnes. Due to geological reasons, the mining company can only create 8 underground tunnels. All 8 ventilation shafts must be accessible from the entrance of the mine. 3

1. 1. The mining company wants to maximise the amount of precious metal it can extract from the new mine. Determine the tunnels the mining company should use.
      3
      1. (ii) Estimate the maximum amount of precious metal the mining company can extract from the new mine. 3
   2. Comment on why the maximum amount of precious metal the mining company can extract from the new mine may be different from your answer to part (a)(ii).
      [0pt] [2 marks]
      3
   3. Before the mining company begins work on the new mine, a government survey prevents the mining company drilling the tunnel represented by \(C F\). Determine the effect, if any, the government survey has on your answers to part (a)(i) and part (a)(ii).

3. \begin{figure}[h] \end{figure} [The weight of the network is \(5 x + 246\) ]

1. 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.
2. 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,
3. use an appropriate algorithm to determine the value of \(x\), showing your working clearly.

3 The diagram shows a simplified map of the main streets in a small town. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246} Some of the junctions have traffic lights, these junctions are labelled A to F .
There are no traffic lights at junctions X and Y .
The numbers show distances, in km, between junctions. Alex needs to check that the traffic lights at junctions A to F are working correctly.

1. Find a route from A to E that has length 2.8 km . Alex has started to construct a table of shortest distances between junctions A to F. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246} For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
2. Complete the copy of the table in the Printed Answer Booklet.
3. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
   Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
4. Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c).

The table shows the least distances, in km, between six towns, A, B, C, D, E and F. Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

1. Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound. \hfill [2]
2. Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Liz's route. \hfill [2]
3. Starting by deleting F, and all of its arcs, find a lower bound for the length of Liz's route. \hfill [3]
4. Use your results to write down the smallest interval which you are confident contains the optimal length of the route. \hfill [1]

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]

This question should be answered on the sheet provided in the answer booklet. A school wishes to link 6 computers. One is in the school office and one in each of rooms \(A\), \(B\), \(C\), \(D\) and \(E\). Cables need to be laid to connect the computers. The school wishes to use a minimum total length of cable. The table shows the shortest distances, in metres, between the various sites.

1. Starting at the school office, use Prim's algorithm to find a minimum spanning tree. Indicate the order in which you select the edges and draw your final tree. [5 marks]
2. Using your answer to part (a), calculate the minimum total length of cable required. [1 mark]

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]

\includegraphics{figure_2} The network in Figure 2 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.

1. Find a minimum spanning tree for the network in Figure 2, showing clearly the order in which you selected the arcs for your tree, using
   1. Kruskal's algorithm, [3]
   2. Prim's algorithm, starting from \(A\). [3]
   Given that footpaths are already in place along \(AB\) and \(FI\) and so should be included in the spanning tree,
2. explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.) [2]

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	\(-\)	48	117	92	\(-\)	\(-\)	\(-\)
\(B\)	48	\(-\)	\(-\)	\(-\)	\(-\)	63	55
\(C\)	117	\(-\)	\(-\)	28	\(-\)	\(-\)	85
\(D\)	92	\(-\)	28	\(-\)	58	132	\(-\)
\(E\)	\(-\)	\(-\)	\(-\)	58	\(-\)	124	\(-\)
\(F\)	\(-\)	63	\(-\)	132	124	\(-\)	\(-\)
\(G\)	\(-\)	55	85	\(-\)	\(-\)	\(-\)	\(-\)

The table shows the lengths, in metres, of the paths between seven vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) in a network N.

1. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. [5]
2. Draw N using the vertices given in Diagram 2 in the answer book. [3]
3. Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length. (The weight of N is 802.) [7]

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]

$$\begin{array}{c|c|c|c|c|c} & M & A & B & C & D & E \\ \hline M & - & 215 & 170 & 290 & 210 & 305 \\ \hline A & 215 & - & 275 & 100 & 217 & 214 \\ \hline B & 170 & 275 & - & 267 & 230 & 200 \\ \hline C & 290 & 100 & 267 & - & 180 & 220 \\ \hline D & 210 & 217 & 230 & 180 & - & 245 \\ \hline E & 305 & 214 & 200 & 220 & 245 & - \end{array}$$ The table shows the cost, in pounds, of linking five automatic alarm sensors, \(A,B,C,D\) and \(E\), and the main reception, \(M\).

1. Use Prim's algorithm, starting from \(M\), to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected. [3]
2. Draw your tree using the vertices given in Diagram 1 in the answer book. [1]
3. Find the total weight of your tree. [1]
4. Explain why it is not necessary to check for cycles when using Prim's algorithm. [2]

(Total 7 marks)

\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)

The following network shows the lengths, in miles, of roads connecting nine villages, \(A\), \(B\), ..., \(I\). \includegraphics{figure_3}

1. 1. Use Prim's algorithm starting from \(E\), showing the order in which you select the edges, to find a minimum spanning tree for the network. [4]
   2. State the length of your minimum spanning tree. [1]
   3. Draw your minimum spanning tree. [2]
2. On a particular day, village \(B\) is cut off, so its connecting roads cannot be used. Find the length of a minimum spanning tree for the remaining eight villages. [2]

The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics{figure_3}

1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns. [6 marks]
2. State the length of your minimum spanning tree. [1 mark]
3. Draw your minimum spanning tree. [3 marks]
4. If Prim's algorithm, starting at \(B\), had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree. [1 mark]

Answer this question on the insert provided. \includegraphics{figure_2}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight. [5]
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(G\), and all the arcs joined to \(G\), removed. Hence find a lower bound for the travelling salesperson problem on the original network. [3]
3. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the travelling salesperson problem on the original network. [3]

The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles.

	Ayr
250		Birmingham
350	103		Cardiff
235	104	209		Doncaster
446	157	121	261	Exeter

1. Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place. [2]
2. List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. [4]

A sixth vertex, F, is added to the network. The distances, in miles, between F and each of the other places are shown in the table below.

	A	B	C	D	E
Distance from F	200	50	150	59	250

1. Use the weight of the minimum spanning tree from part (ii) to find a lower bound for the length of the minimum tour (cycle) that visits every vertex of the extended network with six vertices. [2]
2. Apply the nearest neighbour method, starting from vertex A, to find an upper bound for the length of the minimum tour (cycle) through the six vertices. [2]
3. Use the two least weight arcs through A to form a least weight path of the form \(SAT\), where \(S\) and \(T\) are two of \(\{B, C, D, E, F\}\), and give the weight of this path. Similarly write down a least weight path of the form \(UEV\), where \(U\) and \(V\) are two of \(\{A, B, C, D, F\}\), and give the weight of this path. You should find that the two paths that you have written down use all six vertices. Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour. [8]

In a factory a network of pipes connects 6 vats, A, B, C, D, E and F. Two separate connectors need to be chosen from the network The table shows the lengths of pipes (metres) connecting the 6 vats.

1. Use Kruskal's algorithm to find a minimum connector. Show the order in which you select pipes, draw your connector and give its total length. [5]
2. Produce a new table excluding the pipes which you selected in part (i). Use the tabular form of Prim's algorithm to find a second minimum connector from this reduced set of pipes. Show your working, draw your connector and give its total length. [7]
3. The factory manager prefers the following pair of connectors: \(\{\)AB, BC, BD, BE, BF\(\}\) and \(\{\)AE, BF, CE, DE, DF\(\}\). Give two possible reasons for this preference. [4]

This question should be answered on the sheet provided. \includegraphics{figure_2} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.

1. Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected. [4 marks]
2. It is decided that a Greek translation is not needed. Find the minimum cost if:
   1. translations to and from Greek are not available,
   2. translations to and from Greek are still available. [3 marks]
3. Comment on your findings. [1 mark]

Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.

1. How would you overcome the problem of having different costs for reverse translations? [1 mark]
2. What algorithm would be suitable to find a computerised solution. [1 mark]
3. State another assumption you have made in answering this question and comment on its validity. [2 marks]

The table below shows the distances, in km, between six towns \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).

	A	B	C	D	E	F
A	\(-\)	85	110	175	108	100
B	85	\(-\)	38	175	160	93
C	110	38	\(-\)	148	156	73
D	175	175	148	\(-\)	110	84
E	108	160	156	110	\(-\)	92
F	100	93	73	84	92	\(-\)

1. Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected. [4]
2. 1. Using your answer to part (a) obtain an initial upper bound for the solution of the travelling salesman problem. [2]
   2. Use a short cut to reduce the upper bound to a value less than 680. [4]
3. Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem. [4]

\includegraphics{figure_4} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

1. Write down the source vertices. [2]

\includegraphics{figure_5} Figure 5 shows a feasible flow through the same network.

1. State the value of the feasible flow shown in Fig. 5. [1]

Taking the flow in Fig. 5 as your initial flow pattern,

1. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow. [6]
2. Show the maximal flow on Diagram 2 and state its value. [3]
3. Prove that your flow is maximal. [2]

A company wishes to transport its products from 3 factories \(F_1\), \(F_2\) and \(F_3\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \includegraphics{figure_5}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added. [2]
2. 1. State the maximum flow along \(SF_1ABR\) and \(SF_2CR\). [2]
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
   Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow. [7]
   2. Prove that your final flow is maximal.

\includegraphics{figure_2} A company has 3 warehouses \(W_1\), \(W_2\) and \(W_3\). It needs to transport the goods stored there to 2 retail outlets \(R_1\) and \(R_2\). The capacities of the possible routes, in van loads per day, are shown in Fig. 2. Warehouses \(W_1\), \(W_2\) and \(W_3\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R_1\) and \(R_2\) can accept 6 and 25 van loads respectively per day.

1. On Diagram 1 on the answer sheet add a supersource \(W\) and a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added. [3]
2. State the maximum flow along
   1. \(W_1W_1R_1R\),
   2. \(W_2CR_2R\).
   [2]
3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flow-augmenting route you find together with its flow. [5]
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. [1]

The table shows the least distances, in km, between five towns, \(A\), \(B\), \(C\), \(D\) and \(E\). Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.

1. Making your method clear, find an initial upper bound starting at \(A\) and using
   1. the minimum spanning tree method, [4]
   2. the nearest neighbour algorithm. [3]
2. By deleting \(E\), find a lower bound. [4]
3. Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down. [1]

(Total 12 marks)

\includegraphics{figure_1} Figure 1 shows a capacitated directed network. The number on each arc is its capacity. \includegraphics{figure_2} Figure 2 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\). [2]
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
3. Use this initial flow and the labelling procedure on Diagram 1 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. Diagram 1 \includegraphics{figure_3} [5]
4. Show your maximal flow pattern on Diagram 2. Diagram 2 \includegraphics{figure_4} [2]
5. Prove that your flow is maximal. [2]

(Total 13 marks)