MST On Complete Graphs
Alan M. Frieze showed that given a complete graph on n vertices, with edge weights that are independent identically distributed random variables with distribution function satisfying, then as n approaches +∞ the expected weight of the MST approaches, where is the Riemann zeta function. Under the additional assumption of finite variance, Frieze also proved convergence in probability. Subsequently, J. Michael Steele showed that the variance assumption could be dropped.
In later work, Svante Janson proved a central limit theorem for weight of the MST.
For uniform random weights in, the exact expected size of the minimum spanning tree has been computed for small complete graphs.
| Vertices | Expected size | Approximative expected size |
|---|---|---|
| 2 | 1 / 2 | 0.5 |
| 3 | 3 / 4 | 0.75 |
| 4 | 31 / 35 | 0.8857143 |
| 5 | 893 / 924 | 0.9664502 |
| 6 | 278 / 273 | 1.0183151 |
| 7 | 30739 / 29172 | 1.053716 |
| 8 | 199462271 / 184848378 | 1.0790588 |
| 9 | 126510063932 / 115228853025 | 1.0979027 |
Read more about this topic: Minimum Spanning Tree
Famous quotes containing the word complete:
“To throw obstacles in the way of a complete education is like putting out the eyes; to deny the rights of property is like cutting off the hands. To refuse political equality is like robbing the ostracized of all self-respect, of credit in the market place, of recompense in the world of work, of a voice in choosing those who make and administer the law, a choice in the jury before whom they are tried, and in the judge who decides their punishment.”
—Elizabeth Cady Stanton (1815–1902)