First Model
Let G be a finite connected graph. To define the random MST on G, make G into a weighted graph by choosing weights randomly, uniformly between 0 and 1 independently for each edge. Now pick the MST from this weighted graph i.e. the spanning tree with the lowest total weight. Almost surely, there would be only one i.e. there would be not 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 (x,y) with x and y both integers 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
Mainly we will think about N as large and be interested in asymptotic properties as N goes to infinity.
Read more about this topic: Random Minimal Spanning Tree
Famous quotes containing the word model:
“The best way to teach a child restraint and generosity is to be a model of those qualities yourself. If your child sees that you want a particular item but refrain from buying it, either because it isn’t practical or because you can’t afford it, he will begin to understand restraint. Likewise, if you donate books or clothing to charity, take him with you to distribute the items to teach him about generosity.”
—Lawrence Balter (20th century)
“When you model yourself on people, you should try to resemble their good sides.”
—Molière [Jean Baptiste Poquelin] (1622–1673)