Minimum Spanning Trees 1
Try VividMath Premium to unlock full access
Time limit: 0
Quiz summary
0 of 4 questions completed
Questions:
- 1
- 2
- 3
- 4
Information
–
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading...
You must sign in or sign up to start the quiz.
You have to finish following quiz, to start this quiz:
Loading...
- 1
- 2
- 3
- 4
- Answered
- Review
-
Question 1 of 4
1. Question
Draw the minimum spanning tree of this network.
Hint
Help VideoCorrect
Nice Job!
Incorrect
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.`QR` `=` `60` `QS` `=` `70` `PT` `=` `70` `ST` `=` `80` `PQ` `=` `85` `QT` `=` `90` `SR` `=` `100` `PR` `=` `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 VideoCorrect
Excellent!
Incorrect
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` and find which one has the lowest value.
`P` `=` `(27,19,``18``)` Next, list down all the vertices connected to vertices `P` and `Q` and find which one has the lowest value.
`PQ` `=` `(27,``19``,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`, `Q`, and `R` is `22`, but using that edge will create a cycle. Therefore, we pick the second lowest value, which is `24`.`PQT` `=` `(27,22, ``24``,31,32)` 
`PQTR` `=` `(27,32,31, ``26``)` Finally, get the sum of the edges of the spanning tree.minimum length `=` `19+18+24+26` `=` `87` `87` -
Question 3 of 4
3. Question
Find the length of the minumum spanning tree of this network.
- (17)
Hint
Help VideoCorrect
Keep Going!
Incorrect
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` `:` `(3,5)` Pick the edge with the lowest weight and draw it in the diagram`A` `:` `(``3``,5)` 
Next, list the edges connected to `A` and `G`, pick the one with the lowest weight and add it to the diagram.`AG` `:` `(5,``4``,8)` 
Next, list the edges connected to `A`, `G` and `B`, pick the one with the lowest weight and add it to the diagram.`AGB` `:` `(8,``2``,7,4)` 
Next, list the edges connected to `A`, `G`, `B` and `C`, pick the one with the lowest weight and add it to the diagram.`AGBC` `:` `(8,7,4,``3``)` 
Next, list the edges connected to `A`, `G`, `B`, `C` and `D`, pick the one with the lowest weight and add it to the diagram.`AGBCD` `:` `(4,8,``3``,5)` 
Next, list the edges connected to `A`, `G`, `B`, `C`, `D` and `E`, pick the one with the lowest weight and add it to the diagram.`AGBCDE` `:` `(``2``,5,8,4)` 
Notice that all the vertices are now connected and we have `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` `=` `17` `17` -
Question 4 of 4
4. Question
Find the length of the minumum spanning tree of this network.
- (12)
Hint
Help VideoCorrect
Exceptional!
Incorrect
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` edges to make a spanning tree for this network, pick the `5` edges with the least value.`FE` `=` `2` `EB` `=` `2` `DC` `=` `2` `EA` `=` `3` `BC` `=` `3` `FA` `=` `4` `ED` `=` `4` `AB` `=` `5` `EC` `=` `5` Now draw the `5` edges with the lowest values in the diagram
Notice that all the vertices are now connected and we have `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` `=` `12` `12`
Quizzes
- Vertices and Edges
- Degrees 1
- Degrees 2
- Degrees 3
- Drawing a Network 1
- Drawing a Network 2
- Completing a Table from a Network Diagram
- Network from Maps and Plans
- Identify Paths and Cycles
- Eulerian Trails and Circuits 1
- Eulerian Trails and Circuits 2
- Identify Spanning Trees
- Minimum Spanning Trees 1
- Minimum Spanning Trees 2
- Shortest Path 1
- Shortest Path 2