Content deleted Content added
Silverfish (talk | contribs) m Stub-sorting. You can help! |
m Finite disambig |
||
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 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.
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
| |||