Random minimum spanning tree

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 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, and the edge weights have a continuous distribution function whose derivative at zero is D > 0, then 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 and ζ(3) ≈ 1.202 is Apéry's constant. For instance, for edge weights that are uniformly distributed on the unit interval, the derivative is D = 1, and the limit is just ζ(3).[1] 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.[2]

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.[3][4]

Random minimum spanning trees of grid graphs may be used for invasion percolation models of liquid flow through a porous medium,[5] and for maze generation.[6]

References

  1. ^ 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
  2. ^ Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", in Chauvin, Brigitte; Flajolet, Philippe; Gardy, Danièle; Mokkadem, Abdelkader (eds.), Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of the 2nd Colloquium, Versailles-St.-Quentin, France, September 16–19, 2002, Trends in Mathematics, Basel: Birkhäuser, pp. 223–245, doi:10.1007/978-3-0348-8211-8_14, ISBN 978-3-0348-9475-3
  3. ^ Goldschmidt, Christina, Random minimum spanning trees, Mathematical Institute, University of Oxford, retrieved 2019-09-13
  4. ^ Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; Miermont, Grégory (2017), "The scaling limit of the minimum spanning tree of the complete graph", Annals of Probability, 45 (5): 3075–3144, arXiv:1301.1664, doi:10.1214/16-AOP1132
  5. ^ 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, ISBN 978-3-642-63923-4.
  6. ^ Foltin, Martin (2011), Automated Maze Generation and Human Interaction (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics.


Stub icon

This graph theory-related article is a stub. You can help Wikipedia by adding missing information.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.