MHB Does Max-Kruskal Algorithm Find the Maximum Spanning Tree?

[evinda]

Hello! (Wave)

Give an algorithm that finds the MST (maximum spanning tree) of a graph $G=(V,E)$.
Prove that the algorithm you gave finds the MST.

I tried the following:

I applied the Kruskal algorithm, but instead of ordering the edges by weights in increasing order I ordered them in decreasing order.

    Max-KRUSKAL(G,w)
    1. A={}
    2. for each vertex v∈ G.V
    3.      MAKE-SET(v)
    4. sort the edges of G.E into decreasing order by weight w
    5. for each edge (u,v) ∈ G.E, taken in decreasing order by weight w
    6.      if FIND-SET(u)!=FIND-SET(v)   
    7.         A=A U {(u,v)}  
    8.         Union(u,v)
    9. return A

To prove that this algorithm finds indeed the MST, we have to prove that the algorithm produces a spanning tree and that the constructed spanning tree is of maximal weight. But could you give me a hint how we could prove the properties Spanning Tree Validity and Maximality ?

 

[evinda]

Or do we suppose that the algorithm does not give the maximum spanning tree, in order to get a contradiction?