Spanning trees and network optimisation Quiz
Studying this course? Keep your progress in one place.
Pick an answer for each. Quizzes never use energy.
5 questions, one answer each
Each answer is checked as you go, with why.
See all 5 questions
1. A connected network has 9 nodes. How many arcs does a spanning tree have?
- A.
- B.
- C.
- D.
2. In Kruskal's algorithm an arc is rejected when
- A. it is the lightest remaining arc
- B. it would form a cycle with arcs already chosen
- C. it is joined to the starting node
- D. its weight is even
3. At each step Prim's algorithm chooses
- A. the lightest arc leaving the starting node
- B. the lightest remaining arc in the whole network
- C. the lightest arc joining a node in the tree to a node not yet in it
- D. the heaviest arc that forms no cycle
4. Two arcs have equal weight. Which is true?
- A. Both are always in the MST
- B. The MST is always unique
- C. Prim's and Kruskal's give different total weights
- D. There may be more than one MST, all with the same total weight
5. A minimum spanning tree gives
- A. the shortest route between any two nodes
- B. the least total weight connecting all nodes
- C. a closed route through every node
- D. the longest route through the network