Algorithms-1 03

MST

Cut property lemma

Cycle property lemma

Reverse-delete algorithm

From the cycle property follows an algorithm that is different from the one learned in the lectures. We can iterate over edges of the graph and delete the heaviest edge from each cycle

Producing different MSTs by sorting edges differently in Kruskal’s algorithm lemma