A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » 3.1 Trees and 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

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