Minimum spanning trees Quiz

1. A network has 8 vertices. How many arcs are in a spanning tree?

• A. $7$
• B. $6$
• C. $8$
• D. $9$

2. Kruskal's algorithm considers an arc whose ends are already joined by arcs chosen earlier. What should you do?

• A. Accept it
• B. Restart with a different vertex
• C. Reject the next arc instead
• D. Reject it

3. Prim's algorithm has built a tree on $\{A,B,C\}$. Which arc can be chosen next?

• A. Any unused arc in the network
• B. The smallest arc overall
• C. The smallest arc joining $\{A,B,C\}$ to another vertex
• D. The largest arc from $A$

4. The arcs of a tree are $AB=4$, $BC=7$, $CD=5$ and $DE=6$. What is the total weight?

• A. $20$
• B. $24$
• C. $26$
• D. $22$

5. A matrix has the first row $-$, 5, 9, 2. What does the entry $9$ show?

• A. An arc between the first and second vertices of weight $9$
• B. An arc between the first and third vertices of weight $9$
• C. The total weight of the tree
• D. The number of arcs