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

# FM 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

## 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