Greedy Algorithm

Lemma 5.28. Running Kruskal's Algorithm until there are only k trees left produces a maxi-min spacing clustering.
Proof. Let S be the Kruskal cut and R any other cut. Then as S and R both cover V ,
∃ i st S _i intersects two blocks of R. _ Wlog, call these blocks R ₁ and R ₂ and as their inter- sections with S _i are non-empty, exist elements a ∈ S _i ∩ R ₁ and d ∈ S _i ∩ R ₂ .
Consider the path a ~ d in S _i . As a ∈ R ₁ and d ∈ R ₂ then there is an edge b ∼ c in
a ~ d crossing R. _ But, recall how the Kruskal forest is built; namely edges are added in
a useful result to know. Fibonacci heaps have a better amortized runtime than most other priority queue data structures. Their name comes from their analysis which involves Fibonacci numbers. While they do have an amortized runtime that is faster, they are very complicated to code. Furthermore, in practice they have has been shown to be slower because they involve more storage and manipulations of nodes.

non-decreasing order of weight. Therefore w ( b, c ) ≤ spacing ( S ). However, as b ∼ c crosses

R , spacing ( R ) ≤ w ( b, c ). Therefore,
spacing ( R ) ≤ w ( b, c ) ≤ spacing ( S ) (5.7) Thus S is optimal to R. _ As R was chosen arbitrarily, S is optimal.
It should be noted that this algorithm gives us something more than just the maxi-min spacing clustering. The structure of each of the k trees gives us an MST for each cluster.

2.