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

jmaths

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

Kruskal's algorithm Problem set B Worked solutions

Skills

  1. The graph shows the cost, in €, of possible cables between six towns. Use Kruskal's algorithm to find a minimum spanning tree.

    1917222831330720ABCDEF

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: DE 2, AC 3, CD 7, AB 8, BD 13, AD 17, BC 19, EF 20, CF 22, CE 30
      • DE 2: add; AC 3: add; CD 7: add; AB 8: add
      • BD 13: reject, cycle B–A–C–D; AD 17: reject, cycle A–C–D; BC 19: reject, cycle B–A–C; EF 20: add
      • Stop: 5 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 2 + 3 + 7 + 8 + 20 = 40

  2. The table shows the lengths, in km, of possible footpaths between five campsites. Every campsite is to be reachable from every other, directly or through other campsites, using the least total length of path. Use Kruskal's algorithm.

    ABCDEA–35742152B35–65136C7465–7538D211375–34E5263834–

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: BE 6, BD 13, AD 21, DE 34, AB 35, CE 38, AE 52, BC 65, AC 74, CD 75
      • BE 6: add; BD 13: add; AD 21: add; DE 34: reject, cycle D–B–E
      • AB 35: reject, cycle A–D–B; CE 38: add
      • Stop: 4 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 6 + 13 + 21 + 38 = 78

  3. The table shows the length, in metres, of possible wires between six sensors. A dash means no wire can be laid. Use Kruskal's algorithm to connect all the sensors with the least wire.

    ABCDEFA–25225941–B25–45––61C2245–506317D59–50–75–E41–6375–23F–6117–23–

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: CF 17, AC 22, EF 23, AB 25, AE 41, BC 45, CD 50, AD 59, BF 61, CE 63, DE 75
      • CF 17: add; AC 22: add; EF 23: add; AB 25: add
      • AE 41: reject, cycle A–C–F–E; BC 45: reject, cycle B–A–C; CD 50: add
      • Stop: 5 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 17 + 22 + 23 + 25 + 50 = 137

In context

  1. A builder wants to heat seven houses. The graph shows the cost, in £100, of possible pipes between the houses. Find the cheapest way to link all the houses.

    216719145825101517ABCDEFG

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: AG 2, BG 5, CE 7, FG 8, EF 10, BF 14, CF 15, DF 16, BD 17, CG 19, AB 25
      • AG 2: add; BG 5: add; CE 7: add; FG 8: add
      • EF 10: add; BF 14: reject, cycle B–G–F; CF 15: reject, cycle C–E–F; DF 16: add
      • Stop: 6 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 2 + 5 + 7 + 8 + 10 + 16 = 48

  2. A city has eight tram stops to be joined by track. The graph shows the cost, in £ million, of possible sections. Find the cheapest way to connect all eight stops.

    3121314242917217261030ABCDEFGH

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: FG 3, EF 7, EG 10, BD 12, DH 13, CH 14, DE 17, BC 21, FH 24, AB 26, DF 29, AC 30
      • FG 3: add; EF 7: add; EG 10: reject, cycle E–F–G; BD 12: add
      • DH 13: add; CH 14: add; DE 17: add; BC 21: reject, cycle B–D–H–C
      • FH 24: reject, cycle F–E–D–H; AB 26: add
      • Stop: 7 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 3 + 7 + 12 + 13 + 14 + 17 + 26 = 92

  3. Six villages are to be linked by roads. The table shows the cost, in £ million, of a road between each pair of villages. Find the cheapest set of roads that links all six.

    ABCDEFA–7721571826B77–60522412C2160–584223D575258–3464E18244234–44F2612236444–

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: BF 12, AE 18, AC 21, CF 23, BE 24, AF 26, DE 34, CE 42, EF 44, BD 52, AD 57, CD 58, BC 60, DF 64, AB 77
      • BF 12: add; AE 18: add; AC 21: add; CF 23: add
      • BE 24: reject, cycle B–F–C–A–E; AF 26: reject, cycle A–C–F; DE 34: add
      • Stop: 5 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 12 + 18 + 21 + 23 + 34 = 108

Stretch

  1. A company plans to link nine servers. The graph shows the cost, in £ thousand, of possible cables. Find the cheapest network that links all nine servers.

    920231524301487325ABCDEFGHI

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: DG 2, EF 3, GI 4, FI 7, BC 8, CF 9, AE 14, AB 15, DF 20, FG 23, EH 25, HI 30
      • DG 2: add; EF 3: add; GI 4: add; FI 7: add
      • BC 8: add; CF 9: add; AE 14: add; AB 15: reject, cycle A–E–F–C–B
      • DF 20: reject, cycle D–G–I–F; FG 23: reject, cycle F–I–G; EH 25: add
      • Stop: 8 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 2 + 3 + 4 + 7 + 8 + 9 + 14 + 25 = 72

  2. The table shows the cost, in £ thousand, of possible direct fibre links between seven laboratories. A dash means no direct link is possible. Find the cheapest way to connect all seven.

    ABCDEFGA––––587667B–––4054–22C–––4913–68D–4049–5677–E58541356–2664F76––7726––G672268–64––

    1. (a) List the edges in the order Kruskal's algorithm adds them to the tree.

      • Edges by weight: CE 13, BG 22, EF 26, BD 40, CD 49, BE 54, DE 56, AE 58, EG 64, AG 67, CG 68, AF 76, DF 77
      • CE 13: add; BG 22: add; EF 26: add; BD 40: add
      • CD 49: add; BE 54: reject, cycle B–D–C–E; DE 56: reject, cycle D–C–E; AE 58: add
      • Stop: 6 edges chosen.

    2. (b) Find the total weight of the minimum spanning tree.

      • 13 + 22 + 26 + 40 + 49 + 58 = 208

jmaths.xyz · AI HL · AHL 1.8 Minimum spanning trees: Kruskal's algorithm