Exam practice: the whole unit Problem set B Worked solutions

The graph shows the ferry routes between six islands. Is it possible to start on one island, finish on a different island, and sail along every route exactly once? Give a reason.

• Degrees: A 2, B 3, C 4, D 4, E 2, F 3.
• Odd degree: B, F (2 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 F

   • AF = 10 by route A-B-D-F

2. (b) A and G

   • AG = 13 by route A-B-D-F-G

3. (c) C and G

   • CG = 12 by route C-D-F-G

4. (d) C and F

   • CF = 9 by route C-D-F
   • The direct road is 12, but the route is shorter.

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

• Nearest neighbour from E: EC (9), CF (11), FB (10), BD (3), DA (9), AE (18).
• Upper bound = 9 + 11 + 10 + 3 + 9 + 18 = 60.

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

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

   • Kruskal on A, B, C, E, F, G: FG (3), AB (4), EG (5), BC (7), AC (9) skipped, BE (10).

2. (b) Write down its total weight.

   • 4 + 7 + 10 + 5 + 3 = 29.

The vertices in the graph represent seven depots of a delivery company. The edges represent the roads between them. The weight on each edge is the driving time in minutes. It is found that the optimum solution starting at G is G-F-C-A-B-D-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 3, C 4, D 4, E 3, F 4, G 2.
   • Odd degree: B, E (2 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 E; (ii) B and F; (iii) E and F; (iv) D and G. [2 marks]

   • CE = 15 (route C-D-E)
   • BF = 12 (route B-C-F)
   • EF = 12 (route E-G-F)
   • DG = 7 (route D-E-G)
   • Full table of shortest distances: AB 10, AC 7, AD 17, AE 22, AF 15, AG 24, BC 4, BD 11, BE 16, BF 12, BG 18, CD 10, CE 15, CF 8, CG 17, DE 5, DF 11, DG 7, EF 12, EG 2, FG 10.

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: GE (2), ED (5), DC (10), CB (4), BA (10), AF (15), FG (10).
   • Upper bound = 2 + 5 + 10 + 4 + 10 + 15 + 10 = 56.
   • 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: BC (4), DE (5), AC (7), CF (8), AB (10) skipped, CD (10).
   • Edges used: BC (4), DE (5), AC (7), CF (8), CD (10).
   • Total weight = 4 + 5 + 7 + 8 + 10 = 34.

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

   • The two shortest distances at G in the table of shortest distances: GE (2) and GD (7).
   • LB = 34 + 2 + 7 = 43.

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 minute, find the lower bound for the total distance in the optimal solution. [3 marks]

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

The table shows the shortest distances, in minutes, 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 F, to find an upper bound.

   • Nearest neighbour from F: FB (11), BA (5), AE (14), ED (10), DC (10), CF (19).
   • Upper bound = 11 + 5 + 14 + 10 + 10 + 19 = 69.

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

   • Delete A. Kruskal on B, C, D, E, F: CD (10), DE (10), BF (11), BE (12). Tree weight = 10 + 10 + 11 + 12 = 43.
   • Two shortest edges at A: AB (5) and AE (14).
   • LB = 43 + 5 + 14 = 62.

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

   • Delete D. Kruskal on A, B, C, E, F: AB (5), BF (11), BE (12), CE (13). Tree weight = 5 + 11 + 12 + 13 = 41.
   • Two shortest edges at D: DC (10) and DE (10).
   • LB = 41 + 10 + 10 = 61.
   • The better lower bound is the larger: 62.