Minimal Spanning Trees

Minimal spanning trees

This post will contain the following information about minimal spanning trees in QCE General Maths.

• What are ‘trees’
• What are spanning trees
• What are minimum spanning trees
• Using Prim’s and Kruskal’s algorithms to find minimum spanning trees

What are ‘trees’?

A tree is a connected graph that contains no cycles, multiple edges or loops. The following videos explain what trees are and provide examples on how to solve questions.

Example:

What are spanning trees

A spanning tree is a tree that connects all of the vertices of a graph. The following videos explain what spanning trees are and provide examples on how to solve questions.

Example:

What is a minimum spanning tree

A minimum spanning tree is a spanning tree with a minimum length. It connects all the vertices together with the minimum total weighting for the edges.

Using Prim’s and/or Kruskal’s algorithms to determine minimum spanning trees

Prim’s Algorithm

Kruskal’s Algorithm