Practice Spanning Trees (2.2) - Minimum Cost Spanning Trees - Design & Analysis of Algorithms - Vol 2

Practice: Spanning Trees

Lesson 2.2Minimum Cost Spanning Trees

Practise this section

9 questions

Flashcard drill
4 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is a spanning tree?
Show hintHide hint
Think about what it means to connect all points without returning to the same point.
Question 2.
How many edges does a spanning tree with n vertices have?
Show hintHide hint
Relate it to the number of vertices.
3Question 3.
What is the definition of a spanning tree?
- A cycle in a graph
- A connected
- acyclic graph covering all vertices
- A disconnected graph
Show hintHide hint
Consider the properties of trees in graph theory.
4Question 4.
True or False: A minimum spanning tree for a graph can have cycles.
- True
- False
Show hintHide hint
Think about the definition of a tree.
Question 5.
Given a complete graph with 5 nodes and the following edge weights: (A-B: 2, A-C: 3, A-D: 1, A-E: 4, B-C: 5, B-D: 3, B-E: 2, C-D: 4, C-E: 1, D-E: 6), find the minimum spanning tree and compute its total weight.
Show hintHide hint
Look for the smallest edges that keep the tree connected.
Question 6.
Design a road restoration plan for a small town affected by a natural disaster. You have the costs of repairing each road between towns. Describe how you would apply Prim's or Kruskal's algorithm.
Show hintHide hint
Outline the costs and visualize the connections before applying the algorithm.

5 more questions in this section. Enroll free to practise them all.