Note: if you cannot remember what a spanning tree is, revise notes for 3.1 Trees and Spanning Trees.
Minimum Spanning Trees
- Most connected graphs will have multiple spanning trees. In a weighted graph, one of these spanning trees will have the lowest weight (i.e. the sum of each edge’s weight is the least). This is known as a minimum spanning tree.
- Minimum spanning trees are commonly used for optimisation problems. For example, when transferring products between towns, it is advantageous to know the fastest way of doing so.