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

jmaths

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

Minimum spanning trees: Prim's algorithm Problem set A Answers

Skills

  1. DA, AE, EB, BC, CF; total 32

  2. GC, CB, GA, GE, EF, CD; total 38

  3. AD, DF, FC, FB, AE; total 43

  4. DF, FG, FE, FC, CB, BA; total 66

In context

  1. 59 km (edges AF, AE, EB, EC, ED)

    1. (a) AB, AG, GC, CD, GE, EF; 270 m
    2. (b) £9 450
    1. (a) BF, FD, DE, EA, AC
    2. (b) 81 km

Stretch

    1. (a) AF, FE, FD, AB, EC; total 68
    2. (b) FE, FD, FA, AB, EC; total 68
    3. (c) The same total weight, 68, and the same edges, added in a different order. All the weights are different, so there is only one minimum spanning tree.
    1. (a) 25
    2. (b) 30; 5 more

jmaths.xyz · AI HL · AHL 1.9 Minimum spanning trees: Prim's algorithm