Random minimum spanning tree

In mathematics, a random minimum spanning tree may be formed by assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph.

When the given graph is a complete graph on n vertices, and the edge weights have a continuous distribution function whose derivative at zero is D > 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 ζ(3)/D, where ζ is the Riemann zeta function and ζ(3) is Apéry's constant. For instance, for edge weights that are uniformly distributed on the unit interval, the derivative is D = 1, and the limit is just ζ(3).

Random minimum spanning trees of grid graphs may be used for invasion percolation models of liquid flow through a porous medium, and for maze generation.

...
Wikipedia