Apply Prim's Algorithm

6. This question should be answered on the sheet provided. A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.

1. Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
   (4 marks)
   A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once. Assuming that the network satisfies the triangle inequality,
2. find an initial upper bound for the length of his journey,
3. improve this upper bound to find an upper bound of less than 575 miles.
4. By deleting Leeds, find a lower bound for his journey.

1 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? The shortest distances between clients, in km, are given in the matrix below.

   	A	B	C	D	E
   A	-	12	8	6	4
   B	12	-	10	8	10
   C	8	10	-	13	10
   D	6	8	13	-	10
   E	4	10	10	10	-

2. 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. The distance from Fiona's house to each client, in km, is given in the table below.

   	A	B	C	D	E
   F	2	11	9	7	5

3. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
4. (a) Find all the cycles that result from using the nearest neighbour method, starting at F .
   (b) Use these to find an upper bound for the length of Fiona's route.
5. 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.

3. The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H. Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.
2. State the weight of the minimum spanning tree.
3. Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy's route.
4. Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
5. State the best upper bound that can be obtained by using your answers to (c) and (d).
6. Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy's route. You must make your method and working clear.
7. Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy's route.

3. \begin{table}[h] \end{table} Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree.
2. State the weight of the minimum spanning tree. \begin{table}[h]

   \cline { 2 - 9 } \multicolumn{1}{c|}{}	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	\(\mathbf { D }\)	\(\mathbf { E }\)	\(\mathbf { F }\)	\(\mathbf { G }\)	\(\mathbf { H }\)
   \(\mathbf { J }\)	31	27	50	29	43	25	49	35

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} Table 2 shows the distances, in miles, between town J and towns A , B , \(\mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .
   Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.
3. Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
4. Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

1. Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
2. State the weight of the minimum spanning tree found in part (a).
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
4. Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
5. 1. Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
   2. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
6. State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
7. By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
   (2) By deleting J and all of its arcs, a lower bound of length 274 miles was found.
8. State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

6 Answer this question on the insert provided. The table shows the distances, in miles, along the direct roads between six villages, \(A\) to \(F\). A dash ( - ) indicates that there is no direct road linking the villages.

1. On the table in the insert, use Prim's algorithm to find a minimum spanning tree. Start by crossing out row A. Show which entries in the table are chosen and indicate the order in which the rows are deleted. Draw your minimum spanning tree and state its total weight.
2. By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.
3. A pply the nearest neighbour method to the table above, starting from \(F\), to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.
   {}

\includegraphics{figure_4} Figure 4 models a network of underground tunnels that have to be inspected. The number on each arc represents the length, in km, of each tunnel. Joe must travel along each tunnel at least once and the length of his inspection route must be minimised. The total weight of the network is 125 km. The inspection route must start and finish at A.

1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. [5]

Given that it is now permitted to start and finish the inspection at two distinct vertices,

1. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. [2]

(Total 7 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]