# Random minimum spanning tree

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Random_minimum_spanning_tree
> Markdown URL: https://mediated.wiki/source/Random_minimum_spanning_tree.md
> Source: https://en.wikipedia.org/wiki/Random_minimum_spanning_tree
> Source revision: 1337486966
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

thumb|upright=1.35|Random minimum spanning tree on the same graph but with randomized weights.

In mathematics, a '''random minimum spanning tree''' may be formed by assigning [independent](/source/Independence_(probability_theory)) random weights from some distribution to the edges of an [undirected graph](/source/undirected_graph), and then constructing the [minimum spanning tree](/source/minimum_spanning_tree) of the graph.

When the given graph is a [complete graph](/source/complete_graph) on {{mvar|n}} vertices, and the edge weights have a continuous [distribution function](/source/Cumulative_distribution_function) whose derivative at zero is {{math|''D'' > 0}}, then the expected weight of its random minimum spanning trees is bounded by a constant, rather than growing as a function of {{mvar|n}}. More precisely, this constant tends in the limit (as {{mvar|n}} goes to infinity) to {{math|''ζ''(3)/''D''}}, where {{mvar|ζ}} is the [Riemann zeta function](/source/Riemann_zeta_function) and {{math|''ζ''(3) ≈ 1.202}} is [Apéry's constant](/source/Ap%C3%A9ry's_constant). For instance, for edge weights that are uniformly distributed on the [unit interval](/source/unit_interval), the derivative is {{math|1=''D'' = 1}}, and the limit is just {{math|''ζ''(3)}}.{{r|frieze}} For other graphs, the expected weight of the random minimum spanning tree can be calculated as an integral involving the [Tutte polynomial](/source/Tutte_polynomial) of the graph.{{r|steele}}

In contrast to [uniformly random spanning trees](/source/uniform_spanning_tree) of complete graphs, for which the typical [diameter](/source/Diameter_(graph_theory)) 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.{{r|goldschmidt|abgm}}

Random minimum spanning trees of [grid graph](/source/grid_graph)s may be used for [invasion percolation](/source/invasion_percolation) models of liquid flow through a porous medium,{{r|d3m3h}} and for [maze generation](/source/maze_generation).{{r|foltin}}

==References==
<references>

<ref name=abgm>{{citation
 | last1 = Addario-Berry | first1 = Louigi
 | last2 = Broutin | first2 = Nicolas
 | last3 = Goldschmidt | first3 = Christina | author3-link = Christina Goldschmidt
 | last4 = Miermont | first4 = Grégory | author4-link = Grégory Miermont
 | doi = 10.1214/16-AOP1132
 | issue = 5
 | journal = [Annals of Probability](/source/Annals_of_Probability)
 | pages = 3075–3144
 | title = The scaling limit of the minimum spanning tree of the complete graph
 | volume = 45
 | year = 2017| doi-access = free
 | arxiv = 1301.1664
 }}</ref>

<ref name=d3m3h>{{citation
 | last1 = Duxbury | first1 = P. M.
 | last2 = Dobrin | first2 = R.
 | last3 = McGarrity | first3 = E.
 | last4 = Meinke | first4 = J. H.
 | last5 = Donev | first5 = A.
 | last6 = Musolff | first6 = C.
 | last7 = Holm | first7 = E. A.
 | contribution = Network algorithms and critical manifolds in disordered systems
 | doi = 10.1007/978-3-642-59293-5_25
 | pages = 181–194
 | publisher = Springer-Verlag
 | series = Springer Proceedings in Physics
 | title = Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, USA, February 24–28, 2003
 | volume = 95
 | year = 2004| isbn = 978-3-642-63923-4
 }}.</ref>

<ref name=foltin>{{citation|url=http://www.martinfoltin.sk/mazes/thesis.pdf|title=Automated Maze Generation and Human Interaction|first=Martin|last=Foltin|series=Diploma Thesis|publisher=Masaryk University, Faculty of Informatics|location=Brno|year=2011}}.</ref>

<ref name=frieze>{{citation
 | last = Frieze | first = A. M. | authorlink = Alan M. Frieze
 | doi = 10.1016/0166-218X(85)90058-7
 | issue = 1
 | journal = [Discrete Applied Mathematics](/source/Discrete_Applied_Mathematics)
 | mr = 770868
 | pages = 47–56
 | title = On the value of a random minimum spanning tree problem
 | volume = 10
 | year = 1985| doi-access = free
 }}</ref>

<ref name=goldschmidt>{{citation|url=https://www.maths.ox.ac.uk/node/30217|title=Random minimum spanning trees|first=Christina|last=Goldschmidt|authorlink=Christina Goldschmidt|publisher=[Mathematical Institute, University of Oxford](/source/Mathematical_Institute%2C_University_of_Oxford)|accessdate=2019-09-13}}</ref>

<ref name=steele>{{citation
 | last = Steele | first = J. Michael | author-link = J. Michael Steele
 | editor1-last = Chauvin | editor1-first = Brigitte
 | editor2-last = Flajolet | editor2-first = Philippe | editor2-link = Philippe Flajolet
 | editor3-last = Gardy | editor3-first = Danièle
 | editor4-last = Mokkadem | editor4-first = Abdelkader
 | contribution = Minimal spanning trees for graphs with random edge lengths
 | doi = 10.1007/978-3-0348-8211-8_14
 | location = Basel
 | pages = 223–245
 | publisher = Birkhäuser
 | series = Trends in Mathematics
 | title = Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of the 2nd Colloquium, Versailles-St.-Quentin, France, September 16–19, 2002
 | year = 2002| isbn = 978-3-0348-9475-3 }}</ref>

</references>
Category:Spanning tree

{{Graph-stub}}

---
Adapted from the Wikipedia article [Random minimum spanning tree](https://en.wikipedia.org/wiki/Random_minimum_spanning_tree) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Random_minimum_spanning_tree?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.