Trees

Trees provide an efficient way to connect vertices in a graph, minimising the resources needed to ensure all vertices are connected.

Use this page to revise the following concepts within trees:

Definitions and Properties

Trees are a type of connected graph that contains no loops, multiple edges, or cycles. They are named for their visual resemblance to a branching structure (see image below). In a tree, the number of edges is always one less than the number of vertices.

graph with vertices A, B, C, D, E, F. Edges connecting A to B, B to C, A to D, D to E, and D to F.

Spanning trees are subgraphs that are trees, connecting all vertices of the original graph without forming any cycles. A given graph can have multiple distinct spanning trees.

For example, the following graph could have the following spanning trees:

graph with vertices A, B, C, D, E. Edges connecting A to B, B to C, B to D, B to E, C to E, and D to E. Three variations of spanning trees are shown in red. One with B to A, B to C, B to D, B to E; one with A to B to C to E to D; one with B to A, B to D to E, and B to C.

In weighted graphs, the weight of a spanning tree is calculated as the sum of the weights of all its edges.

Minimum Spanning Trees

Minimum spanning trees are spanning trees with the smallest total weight among all possible spanning trees. They are commonly used to optimise resources needed to connect all vertices efficiently. We can find minimum spanning trees using Prim’s Algorithm.

Prim’s Algorithm

  1. Select any vertex as a starting point.
  2. Compare all edges connected to the starting vertex and add the edge with the smallest weight to the tree.
  3. Compare all the edges connected to all the vertices already in the tree and add the edge with the smallest weight that connects a new vertex to the tree.
  4. Repeat step 3 until all vertices are included in the tree.

Regardless of the starting point, this method ensures that the spanning tree has the minimum possible weight.

Note

A minimum spanning tree may have multiple valid variations when there are edges of equal weight that could connect a new vertex. While the specific connections between vertices may differ, all variations will still be valid minimum spanning trees with the same total weight.

Solving Connector Problems

Minimum spanning trees are useful for solving connector problems, where the goal is to optimise the connections between vertices while minimising total cost or resources.

Worked Example

A telecommunications company is planning to lay the fibre optic cables to connect the towns \(A, B, C, D, E, F\). The distance, in km, between the towns is represented by the graph below. To minimise the project cost, the company wants to determine the cheapest way to connect all the towns so that every town can communicate with every other town, either directly or indirectly. If the cost of laying the fibre optic cables is directly proportional to the distance between the towns, \(1km=\$5000\). Find the minimal total cost of laying the cables and identify where the connections are required.

graph with vertices A, B, C, D, E, F. Edges connected with weights in brackets: A to B (3), B to C (3), C to D (6), A to E (5), B to E (4), C to E (6), C to F (7), E to F (6), D to F (5).>

The minimum spanning tree is complete as all vertices are connected.

The total weight of the minimum spanning tree is:

\[3+3+4+6+5=21\]

The minimum cost is calculated by:

\[21\times 5000=\$105\space 000\]

The connections for this minimum spanning tree are \(A-B,\  B-C,\  B-E,\  E-F,\  \textrm{and}\space F-D\).