A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » 3.2 Minimum Spanning Trees

3.2 Minimum Spanning Trees

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.

By Inspection

This content is for Master Notes FM members only. Unlock the content by signing up for a membership level - quick and easy!
Log InSign Up