Minimum Spanning Trees 2
Try VividMath Premium to unlock full access
Time limit: 0
Quiz summary
0 of 5 questions completed
Questions:
- 1
- 2
- 3
- 4
- 5
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
- 5
- Answered
- Review
-
Question 1 of 5
1. Question
Find the length of the minumum spanning tree of this network.
- (42)
Hint
Help VideoCorrect
Correct!
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.`AB` `=` `7` `AE` `=` `8` `CD` `=` `8` `BF` `=` `9` `CE` `=` `10` `BC` `=` `12` `FC` `=` `13` `ED` `=` `14` `FE` `=` `15` 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 `=` `7+8+8+9+10` `=` `42` `42` -
Question 2 of 5
2. Question
Find the length of the minimum spanning tree of this network.
- (82)
Hint
Help VideoCorrect
Great Work!
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 `6` edges to make a spanning tree for this network, pick the `6` edges with the least value.`EF` `=` `10` `FG` `=` `10` `GC` `=` `12` `BG` `=` `14` `AE` `=` `16` `BC` `=` `16` `FD` `=` `20` `ED` `=` `22` `EB` `=` `38` `DC` `=` `40` Notice that `AE` has a lower value than `FD`, but since using `AE` will create a cycle, we will be using the next least valued edge, which is `FD`Now draw the `6` 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 `=` `10+10+12+14+16+20` `=` `82` `82` -
Question 3 of 5
3. Question
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) `\text(m)`
Hint
Help VideoCorrect
Nice Job!
Incorrect
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` edges to make a spanning tree for this network, pick the `6` edges with the least value.`10 \text(m)` `10 \text(m)` `30 \text(m)` `50 \text(m)` `60 \text(m)` `60 \text(m)` `70 \text(m)` `80 \text(m)` `85 \text(m)` `90 \text(m)` `100 \text(m)` Now draw the `6` edges with the lowest values in the diagram
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 `=` `10+10+30+50+60+60` `=` `220 \text(m)` Therefore, the least length of pipes that can be used to connect all the locations is `220 \text(m)`.`220 \text(m)` -
Question 4 of 5
4. Question
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)
Hint
Help VideoCorrect
Correct!
Incorrect
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` edges to make a spanning tree for this network, pick the `6` edges with the least value.`$800` `$900` `$1000` `$1100` `$1400` `$1800` `$1900` `$3200` `$3500` `$4000` `$5600` `$5900` Notice that the edge with the value of `$1400` has a lower cost that the edges costing `$1800` and `$1900`, but since using the edge costing `$1400` will create a cycle, we will be using the next two least valued edges instead.Now draw the `6` edges with the lowest values in the diagram
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 `=` `800+900+1000+1100+1800+1900` `=` `$7500` Therefore, the least cost of fiber optic cables that can be used to connect all the locations is `$7500`.`$7500` -
Question 5 of 5
5. Question
The diagram shows a plan for a golf course including a pump `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) `\text(m)`
Hint
Help VideoCorrect
Fantastic!
Incorrect
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` edges to make a spanning tree for this network, pick the `6` edges with the least value.`80 \text(m)` `90 \text(m)` `100 \text(m)` `105 \text(m)` `110 \text(m)` `115 \text(m)` `120 \text(m)` `140 \text(m)` `170 \text(m)` `185 \text(m)` `195 \text(m)` `210 \text(m)` Notice that the edges with the lengths of `115`, `120`, `140` and `170` metres has a lower lengths than than the edge that is `185` metres long, but since using the edges with the lengths of `115`, `120`, `140` and `170` metres will create a cycle, we will be using the edge that is `185` metres long instead.Now draw the `6` edges with the lowest values in the diagram
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 `=` `80+90+100+105+110+185` `=` `670 \text(m)` Therefore, the least length of water hose that can be used to provide water to all the locations is `670 \text(metres)` long.`670 \text(m)`
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