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

Name Date

Kruskal's algorithm Problem set A

Show the edges in order of weight, and say whether each is added or rejected. Check the tree has one fewer edge than vertices.

Difficulty: first skills applying them stretch

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.
    2. (b) Find the total weight of the minimum spanning tree.

  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.
    2. (b) Find the total weight of the minimum spanning tree.

  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.
    2. (b) Find the total weight of the minimum spanning tree.

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.
    2. (b) Find the total weight of the minimum spanning tree.

  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.
    2. (b) Find the total weight of the minimum spanning tree.

  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.
    2. (b) Find the total weight of the minimum spanning tree.

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.
    2. (b) Find the total weight of the minimum spanning tree.

  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.
    2. (b) Find the total weight of the minimum spanning tree.

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