Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Random minimum spanning tree
open-in-new
<p>In mathematics, a random minimum spanning tree may be formed by assigning <a href="/facts/Independence_(probability_theory)/NUzQtnUL">independent</a> random weights from some distribution to the edges of an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a>, and then constructing the <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> of the graph. </p> <p>When the given graph is a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on n vertices, and the edge weights have a continuous <a href="/facts/Cumulative_distribution_function/WaKU8tp4">distribution function</a> whose derivative at zero is <i>D</i> > 0, then the expected weight of its random minimum spanning trees is bounded by a constant, rather than growing as a function of n. More precisely, this constant tends in the limit (as n goes to infinity) to <i>ζ</i>(3)/<i>D</i>, where ζ is the <a href="/facts/Riemann_zeta_function/MnfRu7lY">Riemann zeta function</a> and <i>ζ</i>(3) ≈ 1.202 is <a href="/facts/Ap%C3%A9ry%27s_constant/59do2TbQ">Apéry's constant</a>. For instance, for edge weights that are uniformly distributed on the <a href="/facts/Unit_interval/W4dP8IJo">unit interval</a>, the derivative is <i>D</i> = 1, and the limit is just <i>ζ</i>(3). For other graphs, the expected weight of the random minimum spanning tree can be calculated as an integral involving the <a href="/facts/Tutte_polynomial/RMzCMxTQ">Tutte polynomial</a> of the graph. </p><p>In contrast to <a href="/facts/Uniform_spanning_tree/XrnUglNF">uniformly random spanning trees</a> of complete graphs, for which the typical <a href="/facts/Diameter_(graph_theory)/EmQFKvqa">diameter</a> is proportional to the square root of the number of vertices, random minimum spanning trees of complete graphs have typical diameter proportional to the cube root. </p><p>Random minimum spanning trees of <a href="/facts/Grid_graph/4EHMt1b6">grid graphs</a> may be used for <a href="/facts/Invasion_percolation/eTgE5aJN">invasion percolation</a> models of liquid flow through a porous medium, and for <a href="/facts/Maze_generation/dS9dGW5p">maze generation</a>. </p>