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

FM Minimum Spanning Trees

3.3 Guide to Minimal Connector Problems

Note: if you cannot remember how to construct minimum spanning trees using Prim’s algorithm, revise notes for 3.2 Minimum Spanning Trees.

Guide to Analysing Minimal Connector Problems

  • Minimal connector problems are problems which require the use of a minimum spanning tree.
  • Always use Prim’s algorithm unless otherwise stated as inspection is more error prone and generally slower.
  • It is generally easier to select a starting node with a small amount of edges.
Read More »3.3 Guide to Minimal Connector Problems

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

Read More »3.2 Minimum Spanning Trees