7.04d Travelling salesman lower bound: using minimum spanning tree

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]

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)

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]

This question should be answered on the sheet provided. The table below shows the distances in miles between five villages. Jane lives in village A and is about to take her daughter's friends home to villages B, C, D and E. She will begin and end her journey at A and wishes to travel the minimum distance possible.

	A	B	C	D	E
A	\(-\)	4	7	8	2
B	4	\(-\)	1	5	6
C	7	1	\(-\)	2	7
D	8	5	2	\(-\)	3
E	2	6	7	3	\(-\)

1. Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey. [4 marks]
2. Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles. [2 marks]

This question should be answered on the sheet provided. The table below gives distances, in miles, for a network relating to a travelling salesman problem.

	A	B	C	D	E	F	G
A	\(-\)	83	57	68	103	91	120
B	83	\(-\)	78	63	41	82	52
C	57	78	\(-\)	37	59	63	74
D	68	63	37	\(-\)	60	52	62
E	103	41	59	60	\(-\)	48	51
F	91	82	63	52	48	\(-\)	77
G	120	52	74	62	51	77	\(-\)

1. Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour beginning and ending at A and state the tour. [4 marks]
2. By deleting A, obtain a lower bound for the length of a tour. [4 marks]
3. Hence, write down an inequality which must by satisfied by d, the minimum distance travelled in miles. [1 mark]

A student is trying to find the solution to the travelling salesperson problem for a network. They correctly find two lower bounds for the solution: 15 and 19 They also correctly find two upper bounds for the solution: 48 and 51 Based on the above information only, which of the following pairs give the best lower bound and best upper bound for the solution of this problem? Tick \((\checkmark)\) one box. [1 mark]

Best Lower Bound	Best Upper Bound
15	48	\(\square\)
15	51	\(\square\)
19	48	\(\square\)
19	51	\(\square\)

The diagram represents a map of seven locations (A to G) and the direct road distances (km) between some of them. \includegraphics{figure_3} A delivery driver needs to start from his depot at D, make deliveries at each of A, B, F and G, and finish at D.

1. Write down a route from A to G of length 70 km. [1]

The table shows the length of the shortest path between some pairs of places.

	D	A	B	F	G
D	-
A		-			70
B			-	84
F			84	-
G		70			-

1. 1. Complete the table.
   2. Use the nearest neighbour method on the table, starting at D, to find the length of a cycle through D, A, B, F and G, ignoring possibly repeating E and C. [4]
2. By first considering the table with the row and column for D removed, find a lower bound for the distance that the driver must travel. [2]
3. What can you conclude from your previous answers about the distance that the driver must travel? [1]

A new road is constructed between D and F. Using this road the driver starts from D, makes the deliveries and returns to D having travelled just 172 km.

1. Find the length of the new road if
   1. the driver does not return to D until all the deliveries have been made,
   2. the driver uses the new road twice in making the deliveries. [4]

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]