Note on the structure of Kruskal's algorithm (Q848958): Difference between revisions

Let \(G=(V,E)\) be a connected edge-weighted graph and let \((V,F)\) be its minimal spanning tree constructed by Kruskal's algorithm [\textit{J.B. Kruskal jun.}, ``On the shortest spanning subtree of a graph and the traveling salesman problem,'' Proc.\ Am.\ Math.\ Soc.\ 7, 48--50 (1956; Zbl 0070.18404)]. We capture the evolution of the spanning forest from \((V,\emptyset)\) to \((V,F)\) by a rooted binary tree \(R\) with leaves in \(V\) and internal nodes in \(F\). Let \(h(G)\) denote the height of \(R\). In case of Prim's algorithm we would have \(h(G_n) = n-1\) for every connected graph \(G_n\) on \(n\) vertices. In case of Kruskal's algorithm there is a constant \(c>0\) such that the probability of \(h(G_n) \geq cn\) tends to \(1\) for \(n\to\infty\), and therefore the expected value of \(h(G_n)\) is in \(\Theta(n)\), for three choices of random edge-weights: {\parindent=6mm \begin{itemize}\item[(1)]\(G_n\) is a complete graph on \(n\) independently uniformly distributed random points in \([0,1]^d\) and the edges are weighted by the Euclidean distance, \item[(2)]\(G_n\) is a complete graph on \(n\) vertices and the edge-weights are independently uniformly distributed in \([0,1]\), \item[(3)]\(G_n\) is the Cartesian product of \(d\) paths \(P_k\), \(n=k^d\), and the edge-weights are independently uniformly distributed in \([0,1]\). \end{itemize}}