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

FM Trees and Minimum Connector Problems

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

3.1 Trees and Spanning Trees

Note: if you cannot remember what cycles or loops are, revise notes for 2.1 Introduction to Walks

Trees

  • A tree is a connected network graph which does not contain loops, multiple edges or cycles.
  • One way of thinking about this, is that it is a graph that continuously branches out like a tree.
  • Every connected graph will have at least one subgraph which is a tree.
  • It uses the smallest number of edges to connect the graph.
  • A tree with n vertices has n-1 edges.

Example

Read More »3.1 Trees and Spanning Trees