We are given a simple connected undirected graph G = (V, E) with edge costs c : E → R+. We would like to find a spanning binary tree T rooted a given node r ∈ T such that T has minimum weight. Consider the following modifiedPrim algorithm that works similar to Prim’s MST algorithm: We maintain a tree T (initially set to be r by itself) and in each iteration of the algorithm, we grow T by attaching a new node T in the cheapest possible way such that we do not violate the binary constraint; if it is not possible to grow the tree, we declare the instance to be infeasible. 1: function modifiedPrim(G=(V, E), r) 2: T ← {r} 3: while |T| < |V| do 4: S ← {u ∈ V : u ∈ T and |children(u)| < 2} 5: R ← {u ∈ V : u ∈/ T} 6: if ∃ (u, v) ∈ E with u ∈ S and v ∈ R then 7: let (u, v) be the minimum cost such edge 8: Add (u, v) to T 9: else 10: return infeasible 11: return T How would you either prove the correctness of modifiedPrim or provide a counter-example where it fails to return the correct answer.
We are given a simple connected undirected graph G = (V, E) with edge costs c : E → R+. We would like to find a spanning binary tree T rooted a given node r ∈ T such that T has minimum weight. Consider the following modifiedPrim
1: function modifiedPrim(G=(V, E), r)
2: T ← {r}
3: while |T| < |V| do
4: S ← {u ∈ V : u ∈ T and |children(u)| < 2}
5: R ← {u ∈ V : u ∈/ T}
6: if ∃ (u, v) ∈ E with u ∈ S and v ∈ R then
7: let (u, v) be the minimum cost such edge
8: Add (u, v) to T
9: else
10: return infeasible
11: return T
How would you either prove the correctness of modifiedPrim or provide a counter-example where it fails to return the correct answer.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
