Step 3 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Ordinary Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 3

Follow the worked example and explain why each modelling and calculation step is valid.

A triangle network has edge weights AB=7, BC=10, AC=22. Find the minimum spanning tree weight.

A triangle network has vertices A, B and C. Edge weights: AB = 7, BC = 10 and AC = 22.

Find the minimum spanning tree weight W.

Read it once, slowly. Then copy it onto your page.
  • What is going on? A triangle: three vertices, and every pair is joined. So there are 3 edges.
  • What is fixed? The weights: AB = 7, BC = 10, AC = 22. No units are given.
  • What do they want? One number: the weight W of the cheapest tree that joins A, B and C.
Céim

Ordinary Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 3 of 8

Kruskal's Algorithm

Kruskal's algorithm builds a minimum spanning tree by considering edges in increasing weight order and accepting only those that do not form a cycle.

Why it matters

Checking for cycles prevents you from choosing cheap edges that leave part of the network disconnected.

The worked example

A triangle network has vertices A, B and C. Edge weights: AB = 7, BC = 10 and AC = 22. Find the minimum spanning tree weight W.

How the worked example goes

  1. Read

    • What is going on? A triangle: three vertices, and every pair is joined. So there are 3 edges.
    • What is fixed? The weights: AB = 7, BC = 10, AC = 22. No units are given.
    • What do they want? One number: the weight W of the cheapest tree that joins A, B and C.
  2. Understand

    • How do I picture it?
    • Draw the triangle and write each weight on its edge.
    • A spanning tree on 3 vertices has 3 − 1 = 2 edges. Use all 3 and you get a loop, A–B–C–A.
  3. Reduce

    • Where do I start?
    • Sort the weights: 7 < 10 < 22. So the order is AB, BC, AC.
    • We need 2 edges. Test each one in that order, then add the accepted weights for W.
  4. Solve

    • Take the edges in order.
    • AB = 7: no loop. Accept. Total 7.
    • BC = 10: C is new, no loop. Accept.
  5. Check

    • Is it really the least?
    • A triangle has only 3 spanning trees: leave out one edge each time.
    • AB + BC = 7 + 10 = 17