Random minimum spanning tree: Difference between revisions

Revision as of 21:18, 25 October 2007

Revision as of 17:47, 14 April 2008

Line 3:

==First model==

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 nonot be 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.

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