Wikipédia

„Minimális feszítőfa” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Addbot (vitalap | szerkesztései)
130 152 szerkesztés
a Bot: 18 interwiki link migrálva a Wikidata d:q240464 adatába
38. 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 azonos eloszlású valószínűségi változók, amiknekamelyek <math>F</math>eloszlásfüggvénye eloszlásfüggvényérekielégíti az <math>F'(0) > 0</math> teljesül.egyenlőtlenséget, igaz az az állítás, hogy Haha ''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.
 
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"
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Minimális_feszítőfa”