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/b/

jmaths

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

The Chinese postman problem Problem set B Answers

Skills

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

  2. Repeat BA (5), AF (4), FE (3); route length 59

    1. (a) B, C, F, G
    2. (b) BC (11) + FG (6) = 17; BF (12) + CG (9) = 21; BG (18) + CF (15) = 33
    3. (c) Repeat BC (11), FG (6); length 104

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

    1. (a) 98
    2. (b) 11

In context

    1. (a) 72 km (repeat CD (10))
    2. (b) 288 minutes
    1. (a) BC (9) + DE (7) = 16; BD (4) + CE (15) = 19; BE (11) + CD (13) = 24. Repeat BC (9), DE (7)
    2. (b) 78 km

  3. Repeat AB (7), CD (9); for example A–B–A–D–C–D–E–C–B–F–A; length 84

Stretch

  1. 65; shorter than 67

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

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