Exam practice: the whole unit Problem set A One question at a time

The graph shows the roads between six villages. Can a journey start and finish at different villages and use each road exactly once? Give a reason.

• Degrees: A 2, B 3, C 4, D 3, E 3, F 3.
• Odd degree: B, D, E, F (4 vertices).
• A trail that uses every edge once and ends at a different vertex needs exactly 2 odd vertices.

The graph shows the roads between seven towns, with lengths in km. Find the shortest distance between:

1. (a) A and E

   • AE = 15 by route A-B-E

2. (b) C and G

   • CG = 22 by route C-F-G

3. (c) A and G

   • AG = 23 by route A-B-E-G

4. (d) B and F

   • BF = 16 by route B-D-F

The table shows the shortest distances, in km, between six places. Use the nearest neighbour algorithm, starting at C, to find an upper bound for the travelling salesman problem.

• Nearest neighbour from C: CB (14), BD (10), DA (8), AE (8), EF (11), FC (18).
• Upper bound = 14 + 10 + 8 + 8 + 11 + 18 = 69.

Use the graph. Sketch a minimum spanning tree for the subgraph with vertices A, B, D, E, F, G, then write down its total weight.

1. (a) Write down the edges of the minimum spanning tree of the subgraph without C.

   • Kruskal on A, B, D, E, F, G: DF (2), AB (3), EG (8), FG (9), EF (11) skipped, BE (12).

2. (b) Write down its total weight.

   • 3 + 12 + 2 + 8 + 9 = 34.

The vertices in the graph represent seven villages in a national park. The edges represent the footpaths between them. The weight on each edge is the length of the path in kilometres. It is found that the optimum solution starting at G is G-F-D-C-A-B-E-G. [17 marks]

1. (a) Determine whether it is possible to complete a journey that starts and finishes at different towns and uses each road exactly once. Give a reason for your answer. [2 marks]

   • Degrees: A 2, B 4, C 3, D 3, E 3, F 3, G 2.
   • Odd degree: C, D, E, F (4 vertices).
   • A trail that uses every edge once and ends at a different vertex needs exactly 2 odd vertices.

2. (b) The table of shortest distances between the towns is built from the graph. Find the shortest distance between (i) C and F; (ii) B and G; (iii) D and G; (iv) D and E. [2 marks]

   • CF = 17 (route C-D-F)
   • BG = 14 (route B-E-G)
   • DG = 19 (route D-F-G)
   • DE = 13 (route D-F-E)
   • Full table of shortest distances: AB 14, AC 5, AD 11, AE 19, AF 21, AG 28, BC 13, BD 14, BE 5, BF 7, BG 14, CD 6, CE 18, CF 17, CG 25, DE 13, DF 11, DG 19, EF 2, EG 9, FG 8.

3. (c) Use the nearest neighbour algorithm on the table of shortest distances, starting at G, to find an upper bound for the travelling salesman problem. [3 marks]

   • Nearest neighbour from G: GF (8), FE (2), EB (5), BC (13), CA (5), AD (11), DG (19).
   • Upper bound = 8 + 2 + 5 + 13 + 5 + 11 + 19 = 63.
   • A leg that is not a road uses the route in the table; the bound is still the sum of the table distances.

4. (d) Sketch a minimum spanning tree for the subgraph with vertices A, B, C, D, E, F, and write down its total weight. [4 marks]

   • Kruskal on A, B, C, D, E, F: EF (2), AC (5), BE (5), CD (6), DF (11).
   • Edges used: EF (2), AC (5), BE (5), CD (6), DF (11).
   • Total weight = 2 + 5 + 5 + 6 + 11 = 29.

5. (e) Hence find a lower bound for the travelling salesman problem. [2 marks]

   • The two shortest roads at G: GF (8) and GE (9).
   • LB = 29 + 8 + 9 = 46.

6. (f) Explain one way in which a better lower bound could be found. [1 mark]

   • Delete a different vertex, find the minimum spanning tree of the rest and add that vertex's two shortest edges.
   • Take the largest of the lower bounds.

7. (g) Given that the length of each road shown on the graph is given to the nearest km, find the lower bound for the total distance in the optimal solution. [3 marks]

   • The optimal route has 7 roads and length 58.
   • Each road could be up to 0.5 km too long.
   • Lower bound = 58 − 7 × 0.5 = 54.5.

The table shows the shortest distances, in km, between six places. A route is needed that visits every place and returns to the start.

1. (a) Use the nearest neighbour algorithm, starting at A, to find an upper bound.

   • Nearest neighbour from A: AF (8), FE (6), ED (10), DC (15), CB (8), BA (13).
   • Upper bound = 8 + 6 + 10 + 15 + 8 + 13 = 60.

2. (b) Delete B and find a lower bound.

   • Delete B. Kruskal on A, C, D, E, F: EF (6), DF (7), AF (8), AE (9) skipped, CF (10). Tree weight = 6 + 7 + 8 + 10 = 31.
   • Two shortest edges at B: BC (8) and BA (13).
   • LB = 31 + 8 + 13 = 52.

3. (c) Explain how a better lower bound could be found. Then delete E and state the better of the two lower bounds.

   • Delete E. Kruskal on A, B, C, D, F: DF (7), AF (8), BC (8), CF (10). Tree weight = 7 + 8 + 8 + 10 = 33.
   • Two shortest edges at E: EF (6) and EA (9).
   • LB = 33 + 6 + 9 = 48.
   • The better lower bound is the larger: 52.