Kruskal's Algorithm (Edexcel A-Level Further Mathematics): Revision Notes

Worked Example

Problem:

Find the minimum spanning tree for the following graph:

Step 1: Sort the Edges by Weight

List edges in ascending order:

Step 2: Initialise the MST

Start with an empty MST.

Step 3: Iterate Through the Edges

Add $AB = 5$

• No cycle.

• MST = $\{ AB \}$ Add $AD = 6$

• No cycle.

• MST = $\{ AB, AD \}$ Add $AC = 7$

• No cycle.

• MST = $\{ AB, AD, AC \}$ Skip $CD = 7$

• Adding $CD$ would form a cycle. Add $BD = 8$

• No cycle.

• MST = $\{ AB, AD, AC, BD \}$

Step 4: Check the MST

The MST includes $v-1 = 4-1 = 3$ edges.

Result:

The minimum spanning tree is:

Common Mistakes

1. Skipping Cycle Checks: Always ensure no cycles are formed when adding edges.
2. Incorrect Sorting: Sorting the edges incorrectly leads to errors in the MST.
3. Premature Stopping: Stop only after including $v-1$ edges.
4. Confusion Between Trees: MST is unique only if edge weights are distinct; otherwise, multiple MSTs may exist.
5. Misinterpreting Graph Connectivity: Kruskal's algorithm works only for connected graphs; otherwise, it gives a spanning forest.

Key Formulas and Concepts

1. Minimum Spanning Tree: A subset of edges connecting all vertices with no cycles and minimum total weight.

2. Number of Edges in MST: For $v$ vertices: $v-1$ edges.

3. Cycle Checking: Use disjoint sets (union-find) to ensure no cycles are formed while adding edges.