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:
“The love between man and woman is the greatest and most complete passion the world will ever see, because it is dual, because it is of two opposing kinds.”
—D.H. (David Herbert)