Random minimum spanning tree: Difference between revisions

Revision as of 00:10, 24 October 2007

Latest revision as of 19:48, 20 January 2025

(31 intermediate revisions by 13 users not shown)

Line 1:

In [[mathematics]], a '''random minimalminimum spanning tree''', ormay '''randombe MST''',formed isby a model (actually two related models) for aassigning [[random]] [[treeIndependence (graphprobability theory)|treeindependent]] (seerandom alsoweights [[minimalfrom spanningsome tree]]).distribution Itto mightthe beedges comparedof against thean [[uniformundirected spanning treegraph]], aand differentthen modelconstructing forthe a[[minimum randomspanning tree]] whichof hasthe been researched much more extensivelygraph.

[[File:Random minimum spanning tree.svg|thumb|380px|Random minimum spanning tree on the same graph but with randomized weights.]]

==First model==

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}}

Let ''G'' be a [[finite set|finite]] [[Glossary of graph theory#Connectivity|connected]] [[Graph (mathematics)|graph]]. To define the random MST on ''G'', make ''G'' into a [[Glossary of graph theory#Weight|weighted graph]] by choosing weights randomly, [[Uniform distribution|uniformly]] between 0 and 1 [[Statistical independence|independently]] for each edge. Now pick the [[minimal spanning tree|MST]] from this weighted graph i.e. the [[Spanning tree (mathematics)|spanning tree]] with the lowest total weight. [[Almost surely]], there would be only one i.e. there would be no two distinct spanning trees with identical total weight. This tree (denote it by ''T'') is also a spanning tree for the unweighted graph ''G''. This is the random MST.

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}}

The most important case, and the one that will be discussed in this page, is that the graph ''G'' is a part of a lattice in [[Euclidean space]]. For example, take the vertex set to be all the points in the [[Plane (mathematics)|plane]] (''x'',''y'') with ''x'' and ''y'' both [[integer]]s between 1 and some ''N''. Make this into a graph by putting an edge between every two points with distance 1. This graph will be denoted by

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

:<math>\mathbb{Z}^2_N.</math>

==References==

Mainly we will think about ''N'' as large and be interested in [[asymptotic]] properties as ''N'' goes to infinity.

{{reflist|refs=

<ref name=abgm>{{citation

{{Combin-stub}}

| last1 = Addario-Berry | first1 = Louigi

[[Category:Graph theory]]

| 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

| 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]]

| 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]]

{{CombinGraph-stub}}