Standard 12: Greedy Algs 3: Minimum Spanning Tree
Short description: Apply definition of MST; execute Prim’s and Kruskal’s algorithms; identify complexity.
Relevant notes: Topic D: Greedy Algorithms.
Full description
Apply the definition of Minimum Spanning Tree. Execute greedy MST algorithms on examples; recall the complexity of Prim's algorithm.
Example problem
Part a.
Execute Prim's algorithm on the following graph, starting from $u$. Give the state of the algorithm at each round.
Part b.
Imagine a connected graph on $n$ vertices with $n$ edges. Your friend suggests that a minimum spanning tree can always be found by removing the highest-weight edge. Are they correct? Prove/disprove.
Sample solution
Sample solution.
Part a.
| Round | best_weight(u) | v | w | x | y | vertex popped | edge added |
|---|---|---|---|---|---|---|---|
| 1 | 0 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | u | N/A |
| 2 | 0 | 11 | 8 | $\infty$ | $\infty$ | w | $\{u,w\}$ |
| 3 | 0 | 7 | 8 | 3 | $\infty$ | x | $\{w,x\}$ |
| 4 | 0 | 7 | 8 | 3 | 5 | y | $\{x,y\}$ |
| 5 | 0 | 7 | 8 | 3 | 5 | v | $\{w,v\}$ . |
Part b.
No. Let's suppose there is a cylce of $n-1$ vertices, and one of them is connected to the $n$th vertex by a single edge, which is the highest-weight edge in the graph. That edge has to be part of the minimum spanning tree, as otherwise the graph is disconnected.
Rubric
Rubric.
To pass, a solution must pass both parts.
To pass, a solution must follow the course requirements for writing, and for proofs in Part b.
For Part a, a solution must clearly present the best_weight array at each round and which vertex is popped. It must be correct, up to inconsequential details such as numbering the rounds starting from zero. For Part b, a solution must give a clear family of counterexamples and correctly prove that they are counterexamples.
The numerical rubric for this problem is:
- 4 (Pass, Near-Perfect): correct, clear, concise.
- 3 (Pass, Proficient): correct, possibly not fully clear or concise. The algorithm steps in Part a may be correct, but not very clearly presented. The proof in Part b may be harder to follow or a bit overly complicated.
- 2 (Fail, Progress): May have an incorrect execution of Prim's in Part a and/or incorrect proof in Part b. May be poorly presented or difficult to follow. May have excess unnecessary explanation or discussion.
- 1 (Fail, Wrong Track): Does not appear to be using Prim's algorithm or the definition of MST correctly.