Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-12/problems/b/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.12

Travelling salesman: bounds and practical problems Problem set B Answers

Skills

    1. (a) LB = 22
    2. (b) LB = 19
    3. (c) The lower bound 22, from deleting D: it is the larger.
    1. (a) AC = 23 (route A-B-C); AD = 21 (route A-B-D); CE = 16 (route C-B-E)
    2. (b) UB = 56
    3. (c) E-B-A-B-D-C-B-E, length 56; visited more than once: B

  3. UB = 73: C-A-D-F-B-E-C

In context

    1. (a) LB = 16
    2. (b) The route is optimal: its length 16 equals the lower bound, so no tour is shorter.
    1. (a) AC = 18 (route A-B-D-C); AD = 14 (route A-B-D); BC = 7 (route B-D-C); BF = 12 (route B-E-F); CE = 14 (route C-D-B-E); CF = 19 (route C-D-B-E-F); DE = 10 (route D-B-E); DF = 15 (route D-B-E-F)
    2. (b) UB = 52
    3. (c) A-E-F-E-B-D-C-D-B-A, length 52; visited more than once: B, D, E
    4. (d) LB = 42; the shortest route is between 42 and 52 minutes

Stretch

    1. (a) LB = 48
    2. (b) LB = 49
    3. (c) UB = 62; between 49 and 62; no, the bounds are not equal, so the tour is not shown to be optimal.

jmaths.xyz · AI HL · AHL 1.12 Travelling salesman: bounds and practical problems