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 vertices, and the edge weights have a continuous
distribution function whose derivative at zero is , then the expected weight of its random minimum spanning trees is bounded by a constant, rather than growing as a function of . More precisely, this constant tends in the limit (as goes to infinity) to , where is the
Riemann zeta function
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
and is
Apéry's constant. For instance, for edge weights that are uniformly distributed on the
unit interval, the derivative is , and the limit is just .
In contrast to
uniformly random spanning trees of complete graphs, for which the typical
diameter 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.
Random minimum spanning trees of
grid graphs may be used for
invasion percolation Invasion percolation is a mathematical model of realistic fluid distributions for slow immiscible fluid invasion in porous media, in percolation theory
In statistical physics and mathematics, percolation theory describes the behavior of a networ ...
models of liquid flow through a porous medium, and for
maze generation
Maze generation algorithms are automated methods for the creation of mazes.
Graph theory based methods
A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements ...
.
[.]
References
{{Combin-stub
Spanning tree