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.Higher 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=3, BC=6, AC=14. Find the minimum spanning tree weight.

A triangle network has vertices A, B and C, with edge weights AB = 3, BC = 6 and AC = 14.

Find the minimum spanning tree weight W.

Read it once, slowly. Then copy it onto your page.
  • What is going on? Three vertices, A, B and C, each joined to the other two: a triangle. A triangle is a loop, so not every edge can stay.
  • What is fixed? The weights: AB = 3, BC = 6, AC = 14. Think of them as costs. No units are given.
  • What do they want? One number: W, the total weight of the cheapest tree that joins all three.
Céim

Higher 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 create a cycle.

Why it matters

In an exam, recording edge decisions shows why your network connects every vertex at minimum total weight.

The worked example

A triangle network has vertices A, B and C, with edge weights AB = 3, BC = 6 and AC = 14. Find the minimum spanning tree weight W.

How the worked example goes

  1. Read

    • What is going on? Three vertices, A, B and C, each joined to the other two: a triangle. A triangle is a loop, so not every edge can stay.
    • What is fixed? The weights: AB = 3, BC = 6, AC = 14. Think of them as costs. No units are given.
    • What do they want? One number: W, the total weight of the cheapest tree that joins all three.
  2. Understand

    • How do I picture it?
    • Draw a triangle. Label the corners A, B, C. Write 3 on AB, 6 on BC, 14 on AC.
    • A spanning tree joins all 3 vertices with no cycle, so it has 3 − 1 = 2 edges. One edge of the triangle goes.
  3. Reduce

    • Where do I start?
    • Sort first. Trap: taking the edges in the order the question lists them is not sorting.
    • AB = 3, BC = 6, AC = 14
  4. Solve

    • Take the two cheapest.
    • Why cheapest first is safe: the cheapest edge leaving any group of joined vertices always belongs to some minimum tree.
    • AB = 3: A, B not yet joined. Accept. Total 3.
  5. Check

    • Is it really the least?
    • A triangle has only 3 spanning trees: drop one edge each time. Price all three.
    • AB + BC: 3 + 6 = 9