Minimum Spanning Trees and Kruskal’s Algorithm (AQA A-Level Further Maths): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What is a spanning tree of a graph?
What is a spanning tree of a graph?
A sub-graph connecting all vertices w/o cycles
For a graph with vertices, how many edges does a spanning tree have?
For a graph with vertices, how many edges does a spanning tree have?
edges
What is a minimum spanning tree?
What is a minimum spanning tree?
The spanning tree with the lowest total weight
Why is Kruskal's algorithm called a greedy algorithm?
Why is Kruskal's algorithm called a greedy algorithm?
It grabs the smallest edge without planning ahead
What is the first step in Kruskal's algorithm?
What is the first step in Kruskal's algorithm?
Select the edge with the smallest weight
When applying Kruskal's algorithm, what should you do if an edge would create a cycle?
When applying Kruskal's algorithm, what should you do if an edge would create a cycle?
Reject it and move to the next edge
A graph has 8 vertices. How many edges are needed for its spanning tree?
A graph has 8 vertices. How many edges are needed for its spanning tree?
7 edges
When should you stop applying Kruskal's algorithm?
When should you stop applying Kruskal's algorithm?
When all vertices are connected
How should you handle edges with equal weights in Kruskal's algorithm?
How should you handle edges with equal weights in Kruskal's algorithm?
Choose one at random; either is valid
What is another name for a spanning tree?
What is another name for a spanning tree?
A connector