Minimum Spanning Trees 1

Topics

Precalculus

Networks

Minimum Spanning Trees

Minimum Spanning Trees 1

Try VividMath Premium to unlock full access

Start Free Trial

Lets see your results!

Points

Score

Time

Retry Quiz

Answered
Review

Question 1 of 4

1. Question
Draw the minimum spanning tree of this network.
- 1.
- 2.
- 3.
- 4.
Hint

Help Video
Correct

Nice Job!
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

A minimum spanning tree is a spanning tree of a network made with the minimum sum of edges available.

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

Next, determine which of the edges has the lowest weight or value.

$Q R$ $QR$ $=$ $=$ $60$ $60$

$Q S$ $QS$ $=$ $=$ $70$ $70$

$P T$ $PT$ $=$ $=$ $70$ $70$

$S T$ $ST$ $=$ $=$ $80$ $80$

$P Q$ $PQ$ $=$ $=$ $85$ $85$

$Q T$ $QT$ $=$ $=$ $90$ $90$

$S R$ $SR$ $=$ $=$ $100$ $100$

$P R$ $PR$ $=$ $=$ $110$ $110$

Now use the edges with the lowest weights to create a spanning tree.

These diagram fits the criteria of a spanning tree and also uses the edges with the minimum weight.
Question 2 of 4

2. Question
Find the length of the minimum spanning tree of this network.
- (87)
Hint

Help Video
Correct

Excellent!
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

A minimum spanning tree is a spanning tree of a network made with the minimum sum of edges available.

First, list down all the vertices connected to vertex $P$ $P$ and find which one has the lowest value.

$P$ $P$ $=$ $=$ $(27, 19,$ $(27,19,$ $18$ $18$ $)$ $)$

Next, list down all the vertices connected to vertices $P$ $P$ and $Q$ $Q$ and find which one has the lowest value.

$P Q$ $PQ$ $=$ $=$ $(27,$ $(27,$ $19$ $19$ $, 22, 24)$ $,22,24)$

Keep doing this process until you have all the vertices connected. Keep in mind that a spanning tree cannot have any cycles and will have one less edge than its vertices.

Notice that the lowest value connected to vertices $P$ $P$ , $Q$ $Q$ , and $R$ $R$ is $22$ $22$ , but using that edge will create a cycle. Therefore, we pick the second lowest value, which is $24$ $24$ .

$P Q T$ $PQT$ $=$ $=$ $(27, 22,$ $(27,22,$ $24$ $24$ $, 31, 32)$ $,31,32)$

$P Q T R$ $PQTR$ $=$ $=$ $(27, 32, 31,$ $(27,32,31,$ $26$ $26$ $)$ $)$

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

minimum length $=$ $=$ $19 + 18 + 24 + 26$ $19+18+24+26$

$=$ $=$ $87$ $87$

$87$ $87$
Question 3 of 4

3. Question
Find the length of the minumum spanning tree of this network.
- (17)
Hint

Help Video
Correct

Keep Going!
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

Prim’s Algorithm is a method of finding a minimum spanning tree by continuously listing the edges connected to a vertex and picking the edges with the lowest weight.

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

Next, pick a starting vertex and list down the value of the edges connected to it. We can start at vertex $A$ $A$ .

$A$ $A$ $:$ $:$ $(3, 5)$ $(3,5)$

Pick the edge with the lowest weight and draw it in the diagram

$A$ $A$ $:$ $:$ $($ $($ $3$ $3$ $, 5)$ $,5)$

Next, list the edges connected to $A$ $A$ and $G$ $G$ , pick the one with the lowest weight and add it to the diagram.

$A G$ $AG$ $:$ $:$ $(5,$ $(5,$ $4$ $4$ $, 8)$ $,8)$

Next, list the edges connected to $A$ $A$ , $G$ $G$ and $B$ $B$ , pick the one with the lowest weight and add it to the diagram.

$A G B$ $AGB$ $:$ $:$ $(8,$ $(8,$ $2$ $2$ $, 7, 4)$ $,7,4)$

Next, list the edges connected to $A$ $A$ , $G$ $G$ , $B$ $B$ and $C$ $C$ , pick the one with the lowest weight and add it to the diagram.

$A G B C$ $AGBC$ $:$ $:$ $(8, 7, 4,$ $(8,7,4,$ $3$ $3$ $)$ $)$

Next, list the edges connected to $A$ $A$ , $G$ $G$ , $B$ $B$ , $C$ $C$ and $D$ $D$ , pick the one with the lowest weight and add it to the diagram.

$A G B C D$ $AGBCD$ $:$ $:$ $(4, 8,$ $(4,8,$ $3$ $3$ $, 5)$ $,5)$

Next, list the edges connected to $A$ $A$ , $G$ $G$ , $B$ $B$ , $C$ $C$ , $D$ $D$ and $E$ $E$ , pick the one with the lowest weight and add it to the diagram.

$A G B C D E$ $AGBCDE$ $:$ $:$ $($ $($ $2$ $2$ $, 5, 8, 4)$ $,5,8,4)$

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 $=$ $=$ $3 + 2 + 4 + 3 + 3 + 2$ $3+2+4+3+3+2$

$=$ $=$ $17$ $17$

$17$ $17$
Question 4 of 4

4. Question
Find the length of the minumum spanning tree of this network.
- (12)
Hint

Help Video
Correct

Exceptional!
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.

$F E$ $FE$ $=$ $=$ $2$ $2$

$E B$ $EB$ $=$ $=$ $2$ $2$

$D C$ $DC$ $=$ $=$ $2$ $2$

$E A$ $EA$ $=$ $=$ $3$ $3$

$B C$ $BC$ $=$ $=$ $3$ $3$

$F A$ $FA$ $=$ $=$ $4$ $4$

$E D$ $ED$ $=$ $=$ $4$ $4$

$A B$ $AB$ $=$ $=$ $5$ $5$

$E C$ $EC$ $=$ $=$ $5$ $5$

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 $=$ $=$ $2 + 3 + 2 + 3 + 2$ $2+3+2+3+2$

$=$ $=$ $12$ $12$

$12$ $12$

Minimum Spanning Trees 1

Try VividMath Premium to unlock full access

Quiz summary

Information

1. Question

Hint

Nice Job!

2. Question

Hint

Excellent!

3. Question

Hint

Keep Going!

4. Question

Hint

Exceptional!

Quizzes

$Q R$ $QR$	$=$ $=$	$60$ $60$
$Q S$ $QS$	$=$ $=$	$70$ $70$
$P T$ $PT$	$=$ $=$	$70$ $70$
$S T$ $ST$	$=$ $=$	$80$ $80$
$P Q$ $PQ$	$=$ $=$	$85$ $85$
$Q T$ $QT$	$=$ $=$	$90$ $90$
$S R$ $SR$	$=$ $=$	$100$ $100$
$P R$ $PR$	$=$ $=$	$110$ $110$

minimum length	$=$ $=$	$19 + 18 + 24 + 26$ $19+18+24+26$
	$=$ $=$	$87$ $87$

minimum length	$=$ $=$	$3 + 2 + 4 + 3 + 3 + 2$ $3+2+4+3+3+2$
	$=$ $=$	$17$ $17$

$F E$ $FE$	$=$ $=$	$2$ $2$
$E B$ $EB$	$=$ $=$	$2$ $2$
$D C$ $DC$	$=$ $=$	$2$ $2$
$E A$ $EA$	$=$ $=$	$3$ $3$
$B C$ $BC$	$=$ $=$	$3$ $3$
$F A$ $FA$	$=$ $=$	$4$ $4$
$E D$ $ED$	$=$ $=$	$4$ $4$
$A B$ $AB$	$=$ $=$	$5$ $5$
$E C$ $EC$	$=$ $=$	$5$ $5$

minimum length	$=$ $=$	$2 + 3 + 2 + 3 + 2$ $2+3+2+3+2$
	$=$ $=$	$12$ $12$