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:
“For true poetry, complete poetry, consists in the harmony of contraries. Hence, it is time to say aloud—and it is here above all that exceptions prove the rule—that everything that exists in nature exists in art.”
—Victor Hugo (1802–1885)