We will develop a new algorithm for finding minimum spanning trees. It is based

Question

We will develop a new algorithm for finding minimum spanning trees. It is based on the following property: Pick any cycle in the graph, and let e be the heaviest edge in that cycle. Then there is a MST that does not contain e.

New algorithm is :

Sort the edges by their weights in decreasing order

For each edge e (picking in decreasing order),

if it is part of a cycle, remove it from G

Return the resulting G

Assume this property is correct , prove the algorithm is correct, please explain correctly.Please don't copy from other website!!!

Explanation / Answer

A minimum spanning tree does not contain cycles. So cycles need to be broken meaning
we need to remove the edges that form cycle. And to acheive minimum spannibg tree we
need to remove the heaviest edges.If the edge is not forming the cycle then it will
certainly be in the MST irrespective of its weight.

We can prove the correctness of the algorithm with contradiction.

Assuming the MST given by the alogorithm is not the MST and there is MST whose
cost is lower than the cost of this MST. The algorithm works on breaking the cycles with
the heaviest edge as we travers doen the list of sorted w=edges. Now if there is a MST with cost less than this MST , this means that there is atleast one cycle which could have been broken with the choice of the edge that is heavier than the edge chosen by this algorithm. But it is not possible as the algorithm first sorts the edges in decreasing order of weights and it is certain that heaviest edges are considered first in order and hence there is a contradiction because that can happen only when the edges are not sorted in decreasing order and that is not the case.

Hence proved

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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