8.07 Trees

The number added to each edge is called a weight. Often it represent time or distance, here are a few examples.

Approximate travel times, in hours, between some European capitals

Average length of bonds in acetic acid (CH_3COOH), measured in Angstrom

A simple circuit diagram, with resistances measured in Ohms.

These numbers transform the way we look at networks. We will be able to encode a lot more information, and perform more insightful analysis.

If a network has weights on its edges, we can give a weight to the whole network by adding up all the weights. This applies to subnetworks too. Similarly, we can give a weight to any walk by adding up all the weights on the edges chosen in the walk (the weight of a walk is sometimes called its length).

• This network has a weight of 4+5+7+3+6+6+11+5+16+21=84.

• The subnetwork in the middle (highlighted in orange) has weight 4+5+7+3+6=25.

• The red walk on the right has weight 3+5+16+11=35.

A connected network that contains no cycles is called a tree. These have a distinctly tree-like appearance:

Once you leave a vertex on any of these networks, you can’t get back to it without repeating an edge.

A spanning tree is a subnetwork of a connected network that is also a tree. It has no cycles or loops.

Here’s an example:

The network in the centre has its eight different spanning trees arranged around it. You can still get from one vertex to any other, but you can’t get back without repeating an edge.

A connected network that isn’t already a tree can have multiple spanning trees. The network below has 11 possible spanning trees:

This network has weight 4+6+5+2+3+10=30.

Here are all the spanning trees, with their weights. Notice that all the spanning trees have the same number of edges. The spanning tree for a network with n vertices will have (n-1) edges.

The last spanning tree is special, since it has the lowest weight out of all of them. We call it the minimal spanning tree. Sometimes there can be two or more spanning trees with equal lowest weight, in which case they are all minimal spanning trees.

Examples

Example 1

Consider the following graphs.

a

Which of these networks is a tree?

A

B

C

Worked Solution

Create a strategy

Choose a network that does not consist of any loops and cycles (a path that ends where it starts).

Apply the idea

Among the choices, only Option C is a network that does not consist of any loops and cycles as it only passes through each of its vertex only once. So, this means that Option C is a tree.

Watch question walkthrough

b

Why is the following graph not a tree?

A

It is disconnected.

B

It has a loop.

C

It has multiple edges connecting the same vertices.

D

It has a cycle.

Worked Solution

Create a strategy

Consider the definition of a cycle to determine why this particular graph is not a tree.

Apply the idea

Among the choices, the given graph is not a tree because it has a cycle. Based on the given graph, it has a path that starts and ends at the same vertex passing through successive vertices.

So, the correct answer is Option D.

Watch question walkthrough

c

Why is the following graph not a tree?

A

It has a loop.

B

It is disconnected.

C

It has a cycle.

D

It has multiple edges connecting the same vertices.

Worked Solution

Create a strategy

Consider the definition of a loop and disconnected graph to determine why this particular graph is not a tree.

Apply the idea

Based on the given graph, it is a disconnected as there are pairs of vertices (ABC and DEF) that are not connected by any path. Moreover, the graph has a cycle as there are paths that start and finish at the same vertex.

So, the correct answers are Options B and C.

Watch question walkthrough