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/

jmaths

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

Kruskal's algorithm Problem set A One question at a time

Try each question on paper first. Open the working a line at a time, then say whether you had it.

Skills

  1. The graph shows the lengths, in km, of possible pipes between six water tanks. Use Kruskal's algorithm to find a minimum spanning tree.

    1019830515132411ABCDEF

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

      • Edges by weight: AB 5, EF 8, AE 10, DF 11, AD 13, BD 15, AF 19, AC 24, CE 30
      • AB 5: add; EF 8: add; AE 10: add; DF 11: add
      • AD 13: reject, cycle A–E–F–D; BD 15: reject, cycle B–A–E–F–D; AF 19: reject, cycle A–E–F; AC 24: add
      • Stop: 5 edges chosen.

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

      • 5 + 8 + 10 + 11 + 24 = 58

  2. The table shows the distances, in km, between five villages. A road network is to link every village to every other, directly or through other villages, with the least total length. Use Kruskal's algorithm.

    ABCDEA–60557052B60–746169C5574–399D706139–8E526998–

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

      • Edges by weight: DE 8, CE 9, CD 39, AE 52, AC 55, AB 60, BD 61, BE 69, AD 70, BC 74
      • DE 8: add; CE 9: add; CD 39: reject, cycle C–E–D; AE 52: add
      • AC 55: reject, cycle A–E–C; AB 60: add
      • Stop: 4 edges chosen.

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

      • 8 + 9 + 52 + 60 = 129

  3. The table shows the cost, in £ thousand, of possible cables between six schools. A dash means no cable can be laid. Use Kruskal's algorithm to connect all the schools at least cost.

    ABCDEFA––743534–B––56–830C7456–6871–D35–68–50–E3487150–29F–30––29–

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

      • Edges by weight: BE 8, EF 29, BF 30, AE 34, AD 35, DE 50, BC 56, CD 68, CE 71, AC 74
      • BE 8: add; EF 29: add; BF 30: reject, cycle B–E–F; AE 34: add
      • AD 35: add; DE 50: reject, cycle D–A–E; BC 56: add
      • Stop: 5 edges chosen.

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

      • 8 + 29 + 34 + 35 + 56 = 162

In context

  1. A farmer wants to supply water to seven fields. The graph shows the cost, in £100, of possible channels between the fields. Find the cheapest way to link all the fields.

    2513372612819172311ABCDEFG

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

      • Edges by weight: AB 3, BE 7, EF 8, CD 11, CF 12, DF 13, AC 17, FG 19, EG 23, BD 25, AD 26
      • AB 3: add; BE 7: add; EF 8: add; CD 11: add
      • CF 12: add; DF 13: reject, cycle D–C–F; AC 17: reject, cycle A–B–E–F–C; FG 19: add
      • Stop: 6 edges chosen.

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

      • 3 + 7 + 8 + 11 + 12 + 19 = 60

  2. A campus has eight buildings. The graph shows the cost, in £ thousand, of fibre links between them. Find the cheapest way to connect all eight buildings.

    30101981661551426124ABCDEFGH

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

      • Edges by weight: AC 4, DG 5, CD 6, GH 8, DF 10, FG 12, CF 14, BD 15, AE 16, EH 19, EF 26, AB 30
      • AC 4: add; DG 5: add; CD 6: add; GH 8: add
      • DF 10: add; FG 12: reject, cycle F–D–G; CF 14: reject, cycle C–D–F; BD 15: add
      • AE 16: add
      • Stop: 7 edges chosen.

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

      • 4 + 5 + 6 + 8 + 10 + 15 + 16 = 64

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

    ABCDEFA–5140271838B51–3287539C4032–292644D27829–2345E18752623–60F3839444560–

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

      • Edges by weight: BD 8, AE 18, DE 23, CE 26, AD 27, CD 29, BC 32, AF 38, BF 39, AC 40, CF 44, DF 45, AB 51, EF 60, BE 75
      • BD 8: add; AE 18: add; DE 23: add; CE 26: add
      • AD 27: reject, cycle A–E–D; CD 29: reject, cycle C–E–D; BC 32: reject, cycle B–D–E–C; AF 38: add
      • Stop: 5 edges chosen.

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

      • 8 + 18 + 23 + 26 + 38 = 113

Stretch

  1. A rail company plans to link nine cities. The graph shows the cost, in £ million, of possible lines. Find the cheapest network that links all nine cities.

    101282621181327176242ABCDEFGHI

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

      • Edges by weight: DG 2, CF 6, FH 8, EH 10, BD 12, AB 13, HI 17, EF 18, FI 21, CD 24, FG 26, AC 27
      • DG 2: add; CF 6: add; FH 8: add; EH 10: add
      • BD 12: add; AB 13: add; HI 17: add; EF 18: reject, cycle E–H–F
      • FI 21: reject, cycle F–H–I; CD 24: add
      • Stop: 8 edges chosen.

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

      • 2 + 6 + 8 + 10 + 12 + 13 + 17 + 24 = 92

  2. The table shows the cost, in €1000, of possible direct links between seven observatories. A dash means no direct link is possible. Find the cheapest way to connect all seven.

    ABCDEFGA–25–––5326B25––1110–59C–––75–6215D–1175–74–35E–10–74––47F53–62––––G2659153547––

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

      • Edges by weight: BE 10, BD 11, CG 15, AB 25, AG 26, DG 35, EG 47, AF 53, BG 59, CF 62, DE 74, CD 75
      • BE 10: add; BD 11: add; CG 15: add; AB 25: add
      • AG 26: add; DG 35: reject, cycle D–B–A–G; EG 47: reject, cycle E–B–A–G; AF 53: add
      • Stop: 6 edges chosen.

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

      • 10 + 11 + 15 + 25 + 26 + 53 = 140

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