Consider the following reverse greedy algorithm for the spanning tree problem: w

Question

Consider the following reverse greedy algorithm for the spanning tree problem: we start with the input graph G, and in each step, remove the edge of the largest weight that does not disconnect G. The algorithm terminates when there is no such edge (i.e., what remains is a tree). Prove that this algorithm also finds the minimum weight spanning tree Hint: Argue one step at a time (i.e., that the cost of the MST is preserved in each step). Prove this by contradiction. You may also want to use the observation that removing any edge of a tree divides the set of vertices it into two connected pieces. ]

Explanation / Answer

Solution:

The definition of MInimum spanning tree is that:

It is a connected graph with n-1 number of edges which are the smallest n-1 edges of the graph (if not creating a cycle in the MST), where n is the number of vertices in the graph.

The properties of minimum spanning tree are of a graph G(V, E) is:

Suppose the algorithm does not result in the graph in a minimum spanning tree, this means that when the graph is left as a tree which means no other edge can be removed from the graph there is an edge which is there in the remaining graph which is larger than the set of edges which are removed from the graph, which is a contradiction according to the algorithm because the algorithm is removing largest edges one step at a time.

Hence our assumption is wrong and the tree is minimum spanning tree.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.