Random minimum spanning tree

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a random minimum spanning tree may be formed by assigning independent 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 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 . For other graphs, the expected weight of the random minimum spanning tree can be calculated as an integral involving the Tutte polynomial of the graph. 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 models of liquid flow through a porous medium, and for maze generation.

In mathematics, a random minimum spanning tree may be formed by assigning independent 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 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 . For other graphs, the expected weight of the random minimum spanning tree can be calculated as an integral involving the Tutte polynomial of the graph. 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 models of liquid flow through a porous medium, and for maze generation.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1337486966 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001337486966 · captured 1770662993.0 · version history

Cite this page as: encyclopegia.org, “Random minimum spanning tree”, snapshot enwiki-001337486966. https://encyclopegia.org/a/random-minimum-spanning-tree

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.