Content deleted Content added
Added illustration and description. |
|||
| (14 intermediate revisions by 5 users not shown) | |||
Line 1:
In mathematics, a '''random minimum spanning tree''' may be formed by assigning [[Independence (probability theory)|independent]] random weights from some distribution to the edges of an [[undirected graph]], and then constructing the [[minimum spanning tree]] of the graph.
[[File:Random minimum spanning tree.svg|thumb|380px|Random minimum spanning tree on the same graph but with randomized weights.]]
When the given graph is a [[complete graph]] on {{mvar|n}} vertices, and the edge weights have a continuous [[Cumulative distribution function|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]] and {{math|''ζ''(3)}} is [[Apéry's constant]]. For instance, for edge weights that are uniformly distributed on the [[unit interval]], the derivative is {{math|1=''D'' = 1}}, and the limit is just {{math|''ζ''(3)}}.<ref>{{citation▼
| last = Frieze | first = A. M. | authorlink = Alan M. Frieze▼
▲When the given graph is a [[complete graph]] on {{mvar|n}} vertices, and the edge weights have a continuous [[Cumulative distribution function|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|''
| doi = 10.1016/0166-218X(85)90058-7▼
| issue = 1▼
In contrast to [[uniform spanning tree|uniformly random spanning trees]] of complete graphs, for which the typical [[Diameter (graph theory)|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.{{r|goldschmidt|abgm}}
| journal = [[Discrete Applied Mathematics]]▼
| mr = 770868▼
Random minimum spanning trees of [[grid graph]]s may be used for [[invasion percolation]] models of liquid flow through a porous medium,
| pages = 47–56▼
| title = On the value of a random minimum spanning tree problem▼
==References==▼
| volume = 10▼
| year = 1985}}.</ref>▼
<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]]
| 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
▲Random minimum spanning trees of [[grid graph]]s may be used for [[invasion percolation]] models of liquid flow through a porous medium,<ref>{{citation
| last1 = Duxbury | first1 = P. M.
| last2 = Dobrin | first2 = R.
Line 27 ⟶ 42:
| 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
| year = 2004}}.</ref> and for [[maze generation]].<ref>{{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>▼
▲
▲==References==
▲{{reflist}}
<ref name=frieze>{{citation
{{Combin-stub}}▼
▲ | last = Frieze | first = A. M. | authorlink = Alan M. Frieze
▲ | doi = 10.1016/0166-218X(85)90058-7
▲ | issue = 1
▲ | journal = [[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]]|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>
}}
[[Category:Spanning tree]]
| |||