Complete Table by Inspection

8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}

1. 1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
   2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
2. 1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
   2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
3. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 1}

   	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)
   \(P\)	-	25
   \(Q\)	25	-	20	21	23	11
   \(\boldsymbol { R }\)		20	-
   \(\boldsymbol { S }\)		21		-
   \(T\)		23			-	12
   \(\boldsymbol { U }\)		11			12	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
   (3)
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
   (1)
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
   (2)

1. The network above shows the distances, in miles, between seven gift shops, \(A , B\), \(C , D , E , F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances below. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}

   	A	\(B\)	C	\(D\)	\(E\)	\(F\)	\(G\)
   A	-		15	36		53	23
   B		-	17	38	49	80	49
   C	15	17	-	21		62	32
   D	36	38	21	-	11	42
   E		49		11	-	31	61
   \(F\)	53	80	62	42	31	-	30
   \(G\)	23	49	32		61	30	-

   (4)

   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
   \(A\)	-		15	36		53	23
   \(B\)		-	17	38	49	80	49
   \(C\)	15	17	-	21		62	32
   \(D\)	36	38	21	-	11	42
   \(E\)		49		11	-	31	61
   \(F\)	53	80	62	42	31	-	30
   \(G\)	23	49	32		61	30	-

2. Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.
   (3)
3. By deleting A, and all of its arcs, find a lower bound for the route length.
   (4) (Total 11 marks)

1. This question should be answered on the sheet provided.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village \(A\) being Sarah's home village.

1. Illustrate this situation as a complete network showing the shortest distances.
   (2 marks)
2. Use the nearest neighbour algorithm, starting with \(A\), to find an upper bound to the length of a tour beginning and ending at \(A\).
   (2 marks)
3. Interpret the tour found in part (b) in terms of the original network.
   (2 marks)

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
   (2 marks)
2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
3. Interpret the tour found in part (b) in terms of the original network.

4. \begin{figure}[h] \end{figure} Figure 3 models a network of roads. The number on each edge gives the length, in km , of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances in the answer book.
2. Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek's route. Write down the route that gives this upper bound.
3. Interpret the route found in (b) in terms of the towns actually visited.
4. Starting by deleting A and all of its arcs, find a lower bound for the route length. Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G .
5. By considering the pairings of all relevant nodes, find the length of Clive's route. State the edges that need to be traversed twice. You must make your method and working clear.

5 [Figure 2, printed on the insert, is provided for use in this question.]

1. Gill is solving a travelling salesperson problem.
   1. She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5. Write down the best upper bound.
   2. She finds the following lower bounds: \(6.5,7,6.5,5,7\). Write down the best lower bound.
2. George is travelling by plane to a number of cities. He is to start at \(F\) and visit each of the other cities at least once before returning to \(F\). The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
   1. Complete Figure 2 to show the minimum times to travel between all pairs of cities.
   2. Find an upper bound for the minimum total flying time by using the route FTPOMF.
   3. Using the nearest neighbour algorithm starting from \(F\), find an upper bound for the minimum total flying time.
   4. By deleting \(F\), find a lower bound for the minimum total flying time.

6

1. Sarah is solving a travelling-salesman problem.
   1. She finds the following upper bounds: \(32,33,32,32,30,32,32\). Write down the best upper bound.
   2. She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20. Write down the best lower bound.
2. Rob is travelling by train to a number of cities. He is to start at \(M\) and visit each other city at least once before returning to \(M\). The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443} The table below shows the minimum travelling times between all pairs of cities.

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\boldsymbol { B }\)	\(\boldsymbol { E }\)	\(\boldsymbol { L }\)	\(\boldsymbol { M }\)	\(\boldsymbol { N }\)
   \(\boldsymbol { B }\)	-	230	82	102	192
   \(\boldsymbol { E }\)	230	-	148	244	258
   \(\boldsymbol { L }\)	82	148	-	126	110
   \(\boldsymbol { M }\)	102	244	126	-	236
   \(\boldsymbol { N }\)	192	258	110	236	-

   1. Explain why the minimum travelling time from \(M\) to \(N\) is not 283 .
   2. Find an upper bound for the minimum travelling time by using the tour \(M N B E L M\).
   3. Write down the actual route corresponding to the tour \(M N B E L M\).
   4. Use the nearest-neighbour algorithm, starting from \(M\), to find another upper bound for the minimum travelling time of Rob's tour.
      [0pt] [4 marks] QUESTION
      1. (i) The best upper bound is \(\_\_\_\_\) (ii) The best lower bound is \(\_\_\_\_\)

6 The network shows the roads linking a warehouse at \(A\) and five shops, \(B , C , D , E\) and \(F\). The numbers on the edges show the lengths, in miles, of the roads. A delivery van leaves the warehouse, delivers to each of the shops and returns to the warehouse. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-12_1241_1239_484_402}

1. Complete the table, on the page opposite, showing the shortest distances between the vertices.
2. 1. Find the total distance travelled if the van follows the cycle \(A E F B C D A\).
   2. Explain why your answer to part (b)(i) provides an upper bound for the minimum journey length.
3. Use the nearest neighbour algorithm starting from \(D\) to find a second upper bound.
4. By deleting \(A\), find a lower bound for the minimum journey length.
5. Given that the minimum journey length is \(T\), write down the best inequality for \(T\) that can be obtained from your answers to parts (b), (c) and (d).
   [0pt] [1 mark] \section*{Answer space for question 6} REFERENCE

   1. 	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { E }\)	\(\boldsymbol { F }\)
      \(\boldsymbol { A }\)	-	7
      \(\boldsymbol { B }\)	7	-	5
      \(\boldsymbol { C }\)		5	-	4
      \(\boldsymbol { D }\)			4	-	6
      \(\boldsymbol { E }\)				6	-	10
      \(\boldsymbol { F }\)					10	-

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
   (3)
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
   (1)
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
   (2)

\includegraphics{figure_1} Figure 1 shows a network of roads connecting six villages \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\). The lengths of the roads are given in km.

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. [2] The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once. [3]
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages. [1]
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length. [2]