Editing Minimum spanning tree (section)

==MST on complete graphs with random weights==
[[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 <math>F</math> satisfying <math>F'(0) > 0</math>, then as ''n'' approaches [[Extended real number line|+∞]] the expected weight of the MST approaches <math>\zeta(3)/F'(0)</math>, where <math>\zeta</math> is the [[Riemann zeta function]] (more specifically is <math>\zeta(3)</math> [[Apéry's constant]]). Frieze and [[J. Michael Steele|Steele]] also proved convergence in probability. [[Svante Janson]] proved a [[central limit theorem]] for weight of the MST.

For uniform random weights in <math>[0,1]</math>, the exact expected size of the minimum spanning tree has been computed for small complete graphs.<ref>{{citation
 | last = Steele | first = J. Michael | author-link = J. Michael Steele
 | contribution = Minimal spanning trees for graphs with random edge lengths
 | mr = 1940139
 | location = Basel
 | pages = 223–245
 | publisher = Birkhäuser
 | series = Trends Math.
 | title = Mathematics and computer science, II (Versailles, 2002)
 | year = 2002}}</ref>

{| class="wikitable"
|-
!Vertices
!Expected size
!Approximate expected size
|-
|2
|{{center|{{sfrac|1|2}}}}
|0.5
|-
|3
|{{center|{{sfrac|3|4}}}}
|0.75
|-
|4
|{{center|{{sfrac|31|35}}}}
|0.8857143
|-
|5
|{{center|{{sfrac|893|924}}}}
|0.9664502
|-
|6
|{{center|{{sfrac|278|273}}}}
|1.0183151
|-
|7
|{{center|{{sfrac|30739|29172}}}}
|1.053716
|-
|8
|{{center|{{sfrac|199462271|184848378}}}}
|1.0790588
|-
|9
|{{center|{{sfrac|126510063932|115228853025}}}}
|1.0979027
|}