CSC373: MSTs Daniel Zingaro
daniel.zingaro@utoronto.ca
1 Possible Properties of MSTs
For each of the following, prove or disprove the claim.
• If e is a minimum-weight edge in connected graph G (where not all edge weights are necessarily
distinct), then every minimum spanning tree of G contains e.
• If e is a minimum-weight edge in connected graph G with distinct edge weights, then every minimum spanning tree of G contains e.
• If G is a connected graph with distinct edge weights, and e is the maximum-weight edge on some cycle C, then no minimum spanning tree of G contains e.
2 Reverse-Delete
Consider the reverse-delete algorithm to find MSTs:
sort edges by non-increasing weight: w(e_1) >= … >= w(e_m)
T <- E
for j <- 1,2,...,m:
if T - {e_j} is connected:
T <- T - {e_j}
return T
Prove that this algorithm always finds a MST. Use the proof structure from class (proving that every partial solution is “promising” by induction), suitably adapted to fit the algorithm.
3 Implementing Reverse-Delete
Reverse-delete is a neat algorithm, but in practice it is not as useful as Kruskal’s or Prim’s algorithms. Why?? Think about how you would implement reverse-delete. What is the running time? Can you think of a way to improve that running time through suitable use of a data structure? How much better is the running time of Kruskal’s or Prim’s algorithm?