Minimum Spanning Trees and Kruskal’s Algorithm (AQA A-Level Further Maths): Flashcards

Sub-graph connecting all vertices without cycles

$(n-1)$ edges

Spanning tree with lowest total weight

Greedy algorithm

Select edge with smallest weight

Check if it creates a cycle

When all vertices are connected

$n^{n-2}$

Connector

Minimum connector