In mathematics, a random minimum spanning tree may be formed by assigning random weights from some distribution to the edges of an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
, and then constructing the
minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
of the graph.
When the given graph is a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
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 and is
Apéry's constant
In mathematics, Apéry's constant is the sum of the reciprocals of the positive cubes. That is, it is defined as the number
:
\begin
\zeta(3) &= \sum_^\infty \frac \\
&= \lim_ \left(\frac + \frac + \cdots + \frac\right),
\end
...
. For instance, for edge weights that are uniformly distributed on the
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis ...
, the derivative is , and the limit is just .
In contrast to
uniformly random spanning trees of complete graphs, for which the typical
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
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 graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a latti ...
s may be used for
invasion percolation models of liquid flow through a porous medium, and for
maze generation.
[.]
References
{{Combin-stub
Spanning tree