„Minimális feszítőfa” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Teljes gráfok minimális költségű feszítő fái |
táblázat |
||
41. sor:
Alan M. Frieze véges szórás feltételezésével be is látta ezt a konvergenciát. J. Michael Steele megmutatta, hogy ez a feltétel mellőzhető. Svante Janson bebizonyított egy centrális határeloszlás tételt a minimális költségű feszítő fák éleinek költségére.
Kis teljes gráfokra, amiken a költségek egyenletes eloszlásúak a <math>[0,1]</math>intervallumon, egy minimális feszítő fa összsúlya:
{| class="wikitable"
|-
!Csúcsok száma
!Az összköltség várható értéke
!A várható érték közeélítése
|-
|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
|}
==Lásd még==
* [[Gráf]]
| |||