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

The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. \includegraphics{figure_3} \includegraphics{figure_4}

1. Draw the complete network of shortest distances. [2]
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. [2]

A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \includegraphics{figure_5}

1. Draw the extended network and the complete 5-node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.) [3]
2. Produce the shortest distance matrix and the route matrix for the extended 5-node network. [3]
3. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network. [3]
4. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm. [4]
5. In the original 5-node network find a shortest route starting at vertex 1 and using each of the 6 arcs at least once. Give the length of your route. [3]

A network of roads connects the villages \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) The weight on each arc in the network represents the distance, in miles, between adjacent villages. The network is shown in the diagram below. \includegraphics{figure_5}

1. Draw, in the space below, the spanning tree of minimum total length for this road network. [3 marks]
2. Find the total length of the spanning tree drawn in part (a). [1 mark]

Figure 1 shows a network of gas pipes. The numbers on each arc represent the lower and upper capacity for each pipe in \(\text{m}^3 \text{s}^{-1}\) The numbers in the circles represent an initial feasible flow of 73 \(\text{m}^3 \text{s}^{-1}\) through the network. \includegraphics{figure_8}

1. On Figure 1 above, add a supersink \(T\) to the network. [2 marks]
2. Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the page opposite, in your solution. [4 marks]

   Augmenting Path	Flow

   Maximum flow \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
3. Prove that the flow found in part (b) is the maximum flow through the network. [2 marks]
4. A trainee engineer claims that increasing the upper capacity of the pipe \(AG\) will increase the maximum flow through the network, as the flow through this pipe cannot currently be increased. Comment on the validity of the trainee's claim. [2 marks]

The owners of a sports stadium want to install electric car charging points in each of the stadium's nine car parks. An engineer creates a plan which requires installing electrical connections so that each car park is connected, directly or indirectly, to the stadium's main electricity power supply. The engineer produces the network shown below, where the nodes represent the stadium's main electricity power supply \(X\) and the nine car parks \(A\), \(B\), \(\ldots\), \(I\) \includegraphics{figure_5} Each arc represents a possible electrical connection which could be installed. The weight on each arc represents the time, in hours, it would take to install the electrical connection. The electrical connections can only be installed one at a time. To reduce disruption, the owners of the sports stadium want the required electrical connections to be installed in the minimum possible total time.

1. 1. Determine the electrical connections that should be installed. [2 marks]
   2. Find the minimum possible total time needed to install the required electrical connections. [1 mark]
2. Following the installation of the electrical connections, some of the car parks have an indirect connection to the stadium's main electricity power supply. Give one limitation of this installation. [1 mark]

Figure 1 shows a network of water pipes. The number on each arc represents the upper capacity for each pipe in litres per second. The numbers in the circles represent an initial feasible flow of 103 litres per second. \includegraphics{figure_1}

1. On Figure 1 above, add a supersource \(S\) and a supersink \(T\) to the network. [2 marks]
2. Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the opposite page, in your solution. [4 marks]

   Augmenting Path	Extra Flow

   Maximum Flow ______________ litres per second
3. While the flow through the network is at its maximum value, the pipe \(EG\) develops a leak. To repair the leak, an engineer turns off the flow of water through \(EG\) The engineer claims that the maximum flow of water through the network will reduce by 31 litres per second. Comment on the validity of the engineer's claim. [2 marks]

Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F. She wants to find a suitable route that does not involve her driving too far.

1. Which standard network problem does Fiona need to solve? [1]

The shortest distances between clients, in km, are given in the matrix below.

1. Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations. State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. [4]

The distance from Fiona's house to each client, in km, is given in the table below.

1. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route. [2]
2. 1. Find all the cycles that result from using the nearest neighbour method, starting at F. [3]
   2. Use these to find an upper bound for the length of Fiona's route. [2]
3. Fiona wants to drive less than 35 km. Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length. [1]