Lower Bound by Vertex Deletion

3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}

1. By deleting vertex \(U\) and all arcs connected to \(U\), find a lower bound for the length of the shortest cycle that visits every vertex of this network.
2. Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.

4

1. ↓
   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
   A	0	4	5	3	2	5	6
   \(B\)	4	0	1	2	4	7	6
   C	5	1	0	3	4	6	7
   \(D\)	3	2	3	0	2	6	4
   \(E\)	2	4	4	2	0	6	6
   \(F\)	5	7	6	6	6	0	10
   \(G\)	6	6	7	4	6	10	0

   Order in which rows were deleted: \(\_\_\_\_\) \(A\) Minimum spanning tree: A
   • \(D\)
   F
   B E \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_33_28_1302_1101} III
   o D C \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_38_38_1297_1491}
   • G Total weight: \(\_\_\_\_\)
2. \(\_\_\_\_\)
3. \(\_\_\_\_\) Lower bound: \(\_\_\_\_\)
4. Tour: \(\_\_\_\_\) Upper bound: \(\_\_\_\_\)

3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516} Alf wants to cycle from his home at \(A\) to visit each of the other villages and return to \(A\) in the shortest possible time.

1. Which standard network problem does Alf need to solve to find the quickest tour through all the villages?
2. Apply the nearest neighbour method starting at \(A\) to find a tour through all the villages that starts and ends at \(A\). Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(A\) and all the arcs that are directly joined to \(A\). Start building your tree at vertex \(B\). (You do not need to represent the network as a matrix.) Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.
4. Write down a route for Alf that would take him 125 minutes.

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

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 hound for the solution of the travelling salesman problem.
   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)

2. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-1_613_1269_1318_392} The network in the diagram shows the distances, in km , of the cables between seven electricity relay stations \(A , B , C , D , E , F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station. By deleting C, a lower bound for the length of the route is found to be 129 km .

1. Find another lower bound for the length of the route by deleting \(F\). State which is the better lower bound of the two.
2. By inspection, complete the table of least distances. The table can now be taken to represent a complete network.
3. Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route.
   (4) (Total 11 marks)

3. (a) Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem. The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G . The least distance between B and G is \(x \mathrm {~km}\), where \(x > 25\) Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.
(b) Starting by deleting B and all of its arcs, find a lower bound for Preety's route. Preety found the nearest neighbour routes from each of A and C . Given that the sum of the lengths of these routes is 331 km ,
(c) find \(x\), making your method clear.
(d) Write down the smallest interval that you can be confident contains the optimal length of Preety's route. Give your answer as an inequality.