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-10/problems/

jmaths

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

The Chinese postman problem Problem set A Answers

Skills

    1. (a) A 2, B 2, C 3, D 3, E 2; odd vertices C and D
    2. (b) CD (4)
    3. (c) 49

  2. Repeat BC (2), CD (3), DE (4); route length 60

    1. (a) B, C, F, G
    2. (b) BC (13) + FG (11) = 24; BF (8) + CG (15) = 23; BG (19) + CF (21) = 40
    3. (c) Repeat BF (8), CG (15); length 110

  4. For example A–B–C–D–C–E–D–A; length 50

    1. (a) 85
    2. (b) 8

In context

    1. (a) 59 km (repeat CD (7))
    2. (b) 177 minutes
    1. (a) BC (8) + DE (6) = 14; BD (2) + CE (9) = 11; BE (8) + CD (10) = 18. Repeat BD (2), CE (9)
    2. (b) 68 km

  3. Repeat AD (15), BC (4); for example A–B–C–B–F–A–D–C–E–D–A; length 93

Stretch

  1. 78; shorter than 80

    1. (a) 107
    2. (b) No, it is still 107.

jmaths.xyz · AI HL · AHL 1.10 The Chinese postman problem