Minimum Spanning Trees 2

Years

Year 11

Networks

Minimum Spanning Trees

Minimum Spanning Trees 2

Try VividMath Premium to unlock full access

Start Free Trial

Lets see your results!

Points

Score

Time

Retry Quiz

Answered
Review

Question 1 of 5

1. Question
Find the length of the minumum spanning tree of this network.
- (42)
Hint

Help Video
Correct

Correct!
Incorrect
Need Text
Play
Current Time 0:00
/
Duration Time 0:00
Remaining Time -0:00
Stream TypeLIVE
Loaded: 0%
Progress: 0%
0:00
Fullscreen
Video Acceleration:
On
Off

00:00
Mute
Playback Rate
1x
2x
1.5x
1.25x
1x
0.75x
0.5x
Subtitles
subtitles off
Captions
captions off
English
Chapters
Chapters

Kruskal’s Algorithm is a method of finding a minimum spanning tree by selecting the edges by least to most.

First, draw a diagram to plot the vertices of the network.

Next, list down the edges with the values going from least to most. Since we only need $5$ $5$ edges to make a spanning tree for this network, pick the $5$ $5$ edges with the least value.

$A B$ $AB$ $=$ $=$ $7$ $7$

$A E$ $AE$ $=$ $=$ $8$ $8$

$C D$ $CD$ $=$ $=$ $8$ $8$

$B F$ $BF$ $=$ $=$ $9$ $9$

$C E$ $CE$ $=$ $=$ $10$ $10$

$B C$ $BC$ $=$ $=$ $12$ $12$

$F C$ $FC$ $=$ $=$ $13$ $13$

$E D$ $ED$ $=$ $=$ $14$ $14$

$F E$ $FE$ $=$ $=$ $15$ $15$

Now draw the $5$ $5$ edges with the lowest values in the diagram

Notice that all the vertices are now connected and we have $5$ $5$ edges, one less than the number of vertices.

This diagram fits the criteria of a spanning tree and is also using the edges with the minimum weights.

Finally, get the sum of the edges of the spanning tree.

minimum length $=$ $=$ $7 + 8 + 8 + 9 + 10$ $7+8+8+9+10$

$=$ $=$ $42$ $42$

$42$ $42$

Question 2 of 5

Find the length of the minimum spanning tree of this network.

(82)

Question 3 of 5

This network shows the lengths of the pipes needed to connect each location in metres. What is the smallest connection distance between all these points in metres?

(220) $m$ $\text(m)$

Question 4 of 5

This network shows the cost of each fiber optic cable used to connect each location in dollars. What is the minimal cost to connect all of these locations?

$$$ $$$ (7500)

Question 5 of 5

The diagram shows a plan for a golf course including a pump

P

$P$ to distribute the water to the whole course. What is the minimum length of hose in metres that can be used to distribute the water from the pump to all the locations?

(670) $m$ $\text(m)$

Incorrect

Need Text

Play

Remaining Time -0:00

Stream TypeLIVE

Loaded: 0%

Progress: 0%

0:00

Fullscreen

00:00

Mute

Kruskal’s Algorithm is a method of finding a minimum spanning tree by selecting the edges by least to most.

We can use Kruskal’s Algorithm to find the minimum spanning tree of this network.

Start by drawing a diagram to plot the vertices of the network.

Next, list down the edges with the values going from least to most. Since we only need

6

$6$ edges to make a spanning tree for this network, pick the

6

$6$ edges with the least value.

80 m

$80 \text(m)$

90 m

$90 \text(m)$

100 m

$100 \text(m)$

105 m

$105 \text(m)$

110 m

$110 \text(m)$

115 m

$115 \text(m)$

120 m

$120 \text(m)$

140 m

$140 \text(m)$

170 m

$170 \text(m)$

185 m

$185 \text(m)$

195 m

$195 \text(m)$

210 m

$210 \text(m)$

Notice that the edges with the lengths of

115

$115$ ,

120

$120$ ,

140

$140$ and

170

$170$ metres has a lower lengths than than the edge that is

185

$185$ metres long, but since using the edges with the lengths of

115

$115$ ,

120

$120$ ,

140

$140$ and

170

$170$ metres will create a cycle, we will be using the edge that is

185

$185$ metres long instead.

Now draw the

6

$6$ edges with the lowest values in the diagram

Notice that all the vertices are now connected and we have

6

$6$ edges, one less than the number of vertices.

This diagram fits the criteria of a spanning tree and is also using the edges with the minimum weights.

Finally, get the sum of the edges of the spanning tree.

minimum length	$=$ $=$	$80 + 90 + 100 + 105 + 110 + 185$ $80+90+100+105+110+185$
	$=$ $=$	$670 m$ $670 \text(m)$

Therefore, the least length of water hose that can be used to provide water to all the locations is

670 metres

$670 \text(metres)$ long.

670 m

$670 \text(m)$

Try VividMath Premium to unlock full access

Quiz summary

Information

1. Question

Hint

Correct!

2. Question

Hint

Great Work!

3. Question

Hint

Nice Job!

4. Question

Hint

Correct!

5. Question

Hint

Fantastic!

Quizzes

$A B$ $AB$	$=$ $=$	$7$ $7$
$A E$ $AE$	$=$ $=$	$8$ $8$
$C D$ $CD$	$=$ $=$	$8$ $8$
$B F$ $BF$	$=$ $=$	$9$ $9$
$C E$ $CE$	$=$ $=$	$10$ $10$
$B C$ $BC$	$=$ $=$	$12$ $12$
$F C$ $FC$	$=$ $=$	$13$ $13$
$E D$ $ED$	$=$ $=$	$14$ $14$
$F E$ $FE$	$=$ $=$	$15$ $15$

minimum length	$=$ $=$	$7 + 8 + 8 + 9 + 10$ $7+8+8+9+10$
	$=$ $=$	$42$ $42$

$E F$ $EF$	$=$ $=$	$10$ $10$
$F G$ $FG$	$=$ $=$	$10$ $10$
$G C$ $GC$	$=$ $=$	$12$ $12$
$B G$ $BG$	$=$ $=$	$14$ $14$
$A E$ $AE$	$=$ $=$	$16$ $16$
$B C$ $BC$	$=$ $=$	$16$ $16$
$F D$ $FD$	$=$ $=$	$20$ $20$
$E D$ $ED$	$=$ $=$	$22$ $22$
$E B$ $EB$	$=$ $=$	$38$ $38$
$D C$ $DC$	$=$ $=$	$40$ $40$

minimum length	$=$ $=$	$10 + 10 + 12 + 14 + 16 + 20$ $10+10+12+14+16+20$
	$=$ $=$	$82$ $82$

minimum length	$=$ $=$	$10 + 10 + 30 + 50 + 60 + 60$ $10+10+30+50+60+60$
	$=$ $=$	$220 m$ $220 \text(m)$

minimum length	$=$ $=$	$800 + 900 + 1000 + 1100 + 1800 + 1900$ $800+900+1000+1100+1800+1900$
	$=$ $=$	$$ 7500$ $$7500$

$$ 800$ $$800$
$$ 900$ $$900$
$$ 1000$ $$1000$
$$ 1100$ $$1100$
$$ 1400$ $$1400$
$$ 1800$ $$1800$
$$ 1900$ $$1900$
$$ 3200$ $$3200$
$$ 3500$ $$3500$
$$ 4000$ $$4000$
$$ 5600$ $$5600$
$$ 5900$ $$5900$