Random minimum spanning tree
In mathematics, a random minimum spanning tree may be formed by assigning 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 n vertices, the expected weight of its random minimum spanning trees is bounded by a constant, rather than growing as a function of n. More precisely, this constant tends in the limit (as n goes to infinity) to ζ(3)/D, where ζ is the Riemann zeta function, ζ(3) is Apéry's constant, and D is the derivative at zero of the distribution function of the edge weights.[1]
Random minimum spanning trees of grid graphs may be used for invasion percolation models of liquid flow through a porous medium,[2] and for maze generation.[3]
References
- ^ Frieze, A. M. (1985), "On the value of a random minimum spanning tree problem", Discrete Applied Mathematics, 10 (1): 47–56, doi:10.1016/0166-218X(85)90058-7, MR 0770868.
- ^ Duxbury, P. M.; Dobrin, R.; McGarrity, E.; Meinke, J. H.; Donev, A.; Musolff, C.; Holm, E. A. (2004), "Network algorithms and critical manifolds in disordered systems", Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, USA, February 24–28, 2003, Springer Proceedings in Physics, vol. 95, Springer-Verlag, pp. 181–194, doi:10.1007/978-3-642-59293-5_25.
- ^ Foltin, Martin (2011), Automated Maze Generation and Human Interaction (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics.
.svg?lang=en){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |