Minimum spanning trees Quiz

1. A network has 7 vertices. How many edges are in a minimum spanning tree?

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

2. A network has edges $AB=3$, $BC=4$, $AC=5$, $CD=6$, $BD=7$. What is the weight of its minimum spanning tree?

• A. $18$
• B. $12$
• C. $13$
• D. $15$

3. When does Kruskal's algorithm reject an edge?

• A. When it has the largest weight in the network
• B. When it is the first edge of its weight
• C. When it joins a vertex to an end of the tree
• D. When it would form a cycle with accepted edges

4. Edges are $XY=5$, $XZ=4$, $YZ=6$, $YW=7$, $ZW=3$. Prim's algorithm starts at $X$. Which arc is added second?

• A. $ZW$
• B. $XY$
• C. $YZ$
• D. $YW$

5. A student says the path between two vertices in a minimum spanning tree is always the shortest path between them. Which is correct?

• A. True, because the tree uses the smallest edges
• B. True, because the tree is connected
• C. False: the tree minimises total weight, not the length between a pair
• D. False: there is more than one tree