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

jmaths

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

Exam practice: the whole unit Problem set A Answers

Skills

  1. No, it is not possible. There are 4 vertices of odd degree (B, D, E, F); a trail between two different towns needs exactly 2.

    1. (a) 15
    2. (b) 22
    3. (c) 23
    4. (d) 16

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

    1. (a) AB (3), BE (12), DF (2), EG (8), FG (9)
    2. (b) 34

In context

    1. (a) No, it is not possible. There are 4 vertices of odd degree (C, D, E, F); a trail between two different towns needs exactly 2.
    2. (b) CF = 17; BG = 14; DG = 19; DE = 13
    3. (c) UB = 63
    4. (d) Edges EF (2), AC (5), BE (5), CD (6), DF (11); weight 29
    5. (e) LB = 46
    6. (f) Delete a different vertex (and find the lower bound again); the largest lower bound is the best.
    7. (g) 54.5

Stretch

    1. (a) UB = 60
    2. (b) LB = 52
    3. (c) Try deleting a different vertex. Deleting E gives 48; the better lower bound is 52.

jmaths.xyz · AI HL · AHL 1.13 Exam practice: the whole unit