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
