Content deleted Content added
Added illustration and description. |
|||
| (One intermediate revision by one other user 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) ≈ 1.202}} 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)}}.{{r|frieze}} 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.{{r|steele}}
Line 40 ⟶ 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
}}.</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>
Line 71 ⟶ 74:
| 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>
}}
| |||