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

Name Date

Kruskal's algorithm Problem set B

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

Each question matches the question with the same number in set A. Do the ones you got wrong there.

Difficulty: first skills applying them stretch

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

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

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

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

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

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

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

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

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