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

jmaths

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

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

Skills

  1. AB, BD, DE, BC, DF; total 28

  2. BG, GE, GA, ED, EF, DC; total 33

  3. CE, EA, AD, EB, BF; total 31

  4. FC, CG, GD, DE, EA, GB; total 35

In context

  1. 65 km (edges AF, AE, EB, BC, BD)

    1. (a) AB, BE, BF, FC, ED; 330 m
    2. (b) £15 840
    1. (a) BA, AE, EC, CD, BF
    2. (b) 58 km

Stretch

    1. (a) BE, BA, AD, DF, FC; total 22
    2. (b) EB, BA, AD, DF, FC; total 22
    3. (c) The same total weight, 22, and the same edges, added in a different order. All the weights are different, so there is only one minimum spanning tree.
    1. (a) 31
    2. (b) 32; 1 more

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