topic badge

7.01 Trees and spanning trees

Worksheet
Undirected graphs
1

Create an undirected graph using the weights from the following distance tables:

a
ABCD
A-273223
B27-3323
C3233--
D2323--
b
ABCDE
A--6-5
B--957
C69-3-
D-53--
E57---
c
ABCDEF
A-6---1
B6-10--3
C-10-697
D--6-5-
E--95--
F137---
2

For a part of the National Broadband Network, optical fibre communications cables must be run between several towns. The distances (in \text{km}) between the towns are listed in the table below. A "-" indicates that there is no direct route between those towns.

WickepinLake GraceKulinPingaringHydenDumbleyung
Wickepin-13477--79
Lake Grace134-6367-80
Kulin7763-4880103
Pingaring-6748-40146
Hyden--8040--
Dumbleyung7980103146--
a

By first finding the minimal spanning tree of this network, find the minimum length of cabling required.

b

If a change in property access regulations makes it possible to shorten the cabling required between Lake Grace and Pingaring to 50\text{ km}, by how much will the length of cabling decrease?

3

The electrical wiring in an industrial plant needs to connect several areas of the plant. Distances (in metres) between the areas are shown below:

GeneratorCrushingLeachingFilterKilnGrading
Generator-732-4
Crushing7-76--
Leaching37-666
Filter266-94
Kiln--69-5
Grading4-645-
a

By first finding the minimal spanning tree of this network, determine the minimum length of wiring required.

b

If an access way is built, such that it is no longer possible to use the direct connection between the Generator and Filter, calculate the new minimum length of wiring.

4

A 3D printer has a movable print head that produces hot, melted plastic to build up layers of the 3D object. The layers are very thin, and it takes a long time for a printed model to be completed, so the designers of the 3D printers try to make the print head move the shortest possible time to move between separate parts.

A particular design has 5 legs, with the time (in seconds) to traverse directly between pairs of legs given by the following table:

Leg 1Leg 2Leg 3Leg 4Leg 5
Leg 1-1.01.40.51.9
Leg 21.0-0.70.61.2
Leg 31.40.7--1.0
Leg 40.50.6--1.5
Leg 51.91.21.01.5-
a
Determine the minimum time to traverse all 5 legs.
b
There was no time specified to traverse between Leg 3 and Leg 4 because this path was obstructed by another part of the design. How much faster could all 5 legs be traversed if it was possible to traverse directly between Leg 3 and Leg 4 in just 0.2 seconds?
Trees
5

Determine whether each of the following graphs is a tree. If it is not a tree, explain why.

a
b
c
d
e
f
g
h
6

State whether the following statements are true about trees:

a

Adding one edge to any tree creates a new tree.

b

A tree has no Eulerian or Hamiltonian circuits.

c

If you remove any edge from a tree it creates a disconnected graph.

d

A tree has at least one Hamiltonian circuit, but not necessarily an Eulerian circuit.

7

Sarah has three children: Kate, Matt and Tom. Kate has four children, Lisa, Sandy, Amy and Robert. Matt has two sons, Joseph and Chris. Both Tom and Lisa have one child each: Barbara and Alex, respectively.

If the starting vertex represents Sarah, create a tree to represent the parent-child relationships in this family.

8

Bianca is writing a report and needs to create a table of contents. Her report consists of five chapters, each broken down into sections. The first chapter is her introduction, so it has just one section. Her second and third chapters both have three sections, while the fourth chapter has six sections. The fifth and final chapter is the conclusion which again has only one section.

Create a tree that represents the structure of Bianca's table of contents.

9

Mitchell is tracing his family lineage back three generations. His mother's name is Rebecca, and his father's name is Connor. Rebecca's parents are Mabel and Patrick, and Connor's parents are Juliet and Mark. Mitchell does not know Mabel's parents's names, but he knows that Patrick's parents are April and Todd. On the other side, Mitchell knows that Juliet's parents are Daisy and Leonard, and Mark's dad is called Richard. Mitchell does not know the name of Mark's mother.

If the initial vertex represents Mitchell, create a family tree of the last three generations from the information above. Use "Unknown" for the name of any ancestors that he doesn't know the name of.

Spanning trees
10

Determine whether following networks have a spanning tree:

a
b
11

State the definition of:

a

A spanning tree

b

A minimum spanning tree

12

Create a distance table for the following weighted networks.

If there is no edge connecting two particular vertices, represent this with an X.

a
b
c
d
13

The distance table for a weighted network is shown below. Complete the network by labelling the vertices.

ABCDE
A-6--12
B6--89
C---147
D-814--
E1297--
Minimal spanning trees
14

Construct the minimal spanning tree for each weighted network below.

a
b
c
15

In a certain area, the council wanted to lay down new electric cables. The given graph displays the map of the area:

To minimise the cost of cables, the council wants to connect the houses in such a way that they minimise the cable length. Construct a graph that will minimise the cable length.

16

Water pipes need to be laid down in a new area that is undergoing construction. The given graph shows the suggested plan where the numbers represent the lengths of the pipes:

To minimise the cost, the council wants to minimise the total length of water pipes used. Construct a graph that would achieve this.

Prim's algorithm from a table
17

Find the total length of the minimum spanning tree for the network represented by each of the distance table shown below:

a
ABCDE
A--9.44.45.2
B---0.63.0
C9.4--7.45.6
D4.40.67.4-7.6
E5.23.05.67.6-
b
ABCDEF
A-516151-93
B51-5499666
C6154--651
D5199--365
E-6653--
F9366165--
c
ABCDE
A-5-36
B5-8--
C-8--4
D3---1
E6-41-
d
ABCDE
A-6--12
B6--89
C---147
D-814--
E1297--
e
ABCDEF
A--9--6
B----115
C9--3-7
D--3-5-
E-11-5-8
F657-8-
f
ABCDE
A-2312310959
B-8918569
C-17671
D-119
E-
g
ABCDEFG
A-616499657972
B61-6279699453
C6462-90919955
D997990-677881
E65699167-7580
F7994997875-87
G725355818087-
h
ABCDEFG
A-70109010100100
B--10204010
C--80108040
D--6090
E---50
F--80
G-
18

Determine the minimum spanning tree for the given network, by following the steps of Prim's algorithm.

Prim's algorithm from a network
19

The direct flight routes between 5 major cities of the same country are shown in the given graph. Each edge is marked with the distance (in \text{km}) travelled on each route:

To optimise their investment, the operating airline wants to find the minimum spanning tree for the graph.

a

Construct the minimum spanning tree.

b

Using these flight routes, what is the minimum distance connecting these major cities?

20

The following weighted network shows possible connections (and associated costs, in millions of dollars) for connecting rural towns to a common cabled internet service:

To minimise the cost of connecting each town to the network, the minimal spanning tree must be found.

a

How many edges will be a part of a spanning tree for this network?

b

Construct the minimum spanning tree.

c

What is the minimum cost of connecting all of the towns together?

21

At the university, there is a new plan to connect all the campus buildings using underground fiber optic cables. The given network was suggested by the engineer:

The project accountant wanted to minimise the cost of the project. He realised that there are unnecessary cables that could be removed to minimise cable length.

Construct the network that represents the least cost.

22

In a certain area, new underground cables need to be laid to connect electric substations. The graph displays the current connection layout:

Since the project has a limited budget, the engineers have to design a connection layout that uses the minimum cable length.

Construct the graph that represents the connection layout with the least cost.

23

An airplane company wants to redesign their flight routes to make it cost efficient. The network displays the current flight routes:

In order for the flight routes to be efficient, the sum of the route distances needs to be minimised.

Construct the graph that will achieve this.

24

The bus company decided to redesign its travel routes after new roads were built. The network shows the existing routes connecting the towns and the respective times taken to cover the route:

The bus company wants to be time efficient with its routes. Construct the graph that will achieve this.

25

A large amusement park is trying to implement a new security system such that all security posts are connected by electric cabling. The network shows all possible connections and their respective lengths:

Since the project has a limited budget, the engineers have to minimise the length of cabling used. Construct the graph that represents the least costly connections.

26

Urban planners are trying to connect houses in a certain area.

The network represents all possible routes between houses in the area, and the distances between them.

The urban planners wish to create roads that are most distance efficient, and allow them to connect each house.

Construct the graph that is the most distance efficient.

27

The water authority wants to lay water pipes along the roads in order to put a fire hydrant at every node on the network shown on the network. The numbers represent the length of the pipe that connects any two nodes.

To minimise the cost of the operation, the water authority wants to minimise the length of the pipes. Construct the graph that will achieves this.

28

The rangers of a national park want to clear walking tracks to six landmarks in the area. The potential tracks between landmarks are shown in the graph below, along with the number of days required to clear each track for use.

To make a network of tracks in the shortest time, the rangers want to find a minimal spanning tree for the graph. Construct the minimal spanning tree.

Sign up to access worksheet
Get full access to our content with a Mathspace account.

Outcomes

ACMGM101

explain the meaning of the terms tree and spanning tree identify practical examples

ACMGM102

identify a minimum spanning tree in a weighted connected graph either by inspection or by using Prim’s algorithm

ACMGM103

use minimal spanning trees to solve minimal connector problems; for example, minimising the length of cable needed to provide power from a single power station to substations in several towns

What is Mathspace

About Mathspace