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:
“It is ... pathetic to observe the complete lack of imagination on the part of certain employers and men and women of the upper-income levels, equally devoid of experience, equally glib with their criticism ... directed against workers, labor leaders, and other villains and personal devils who are the objects of their dart-throwing. Who doesn’t know the wealthy woman who fulminates against the “idle” workers who just won’t get out and hunt jobs?”
—Mary Barnett Gilson (1877–?)