„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
→Algoritmusok: speciális megközelítések |
Teljes gráfok minimális költségű feszítő fái |
||
37. sor:
Egy másik megközelítésben a gráf csúcsaiba processzorokat helyezünk, amik csak az élek mentén tudnak kommunikálni. Így is kiszámítható a gráf egy minimális költségű feszítő fája.
==Teljes gráfok minimális költségű feszítő fái==
Alan M. Frieze megmutatta, hogy egy ''n'' csúcsú teljes gráfban, ahol az élek költségei egymástól független eloszlású valószínűségi változók, amiknek <math>F</math> eloszlásfüggvényére <math>F'(0) > 0</math> teljesül. Ha ''n'' tart a végtelenbe, akkor a minimális költségű feszítő fák költségének várható értéke tart <math>\zeta(3)/F'(0)</math>-hoz, ahol <math>\zeta</math> a Riemann-féle zéta-függvény.
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.
==Lásd még==
* [[Gráf]]
| |||