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

Problem:

Find the MST for the graph represented by the following weight matrix:

Step 1: Select the Starting Vertex

Choose $A$ (vertex 1) as the starting vertex.

Step 2: Find the Smallest Edge from $A$

Edges from $A$:

• $A \to B = 7, A \to C = 3, A \to D = \infty$
• Smallest edge: $A \to C = :highlight[3]$
• MST =$\{ A, C \}, \, \text{Total Weight: } :highlight[3]$

Step 3: Grow the MST

Edges from $C$:

• $C \to B = 2, C \to D = 8, C \to A = 3$ (already included)
• Smallest edge: $C \to B = :highlight[2]$
• MST =$\{ A, C, B \}, \, \text{Total Weight: } :highlight[3 + 2 = 5]$

Step 4: Add the Remaining Vertex

Edges from $B$:

• $B \to D = 6, B \to C = 2$ (already included), $B \to A = 7$ (already included).
• Smallest edge: $B \to D = :highlight[6]$
• MST =$\{ A, C, B, D \}, \, \text{Total Weight: } :highlight[5 + 6 = 11]$

Result:

The MST connects vertices $A, B, C, D$ with a total weight of 11.

Common Mistakes

1. Incorrect Matrix Initialisation: Ensure the matrix accurately represents the graph, using $\infty$ for missing edges.
2. Double-Counting Edges: Avoid revisiting edges already included in the MST.
3. Choosing Larger Weights: Always select the smallest edge connecting to the MST.
4. Stopping Too Early: Ensure all vertices are included in the MST.
5. Misinterpreting Matrix Entries: Diagonal entries should be $\infty$ or $0$, as no vertex connects to itself.

Key Formulas and Concepts

1. Weight Matrix Representation:

2. MST Properties:

• A spanning tree connects all vertices with v-1 edges.
• The MST minimises the total weight of edges.