„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
a Informatikai portál AWB |
Nincs szerkesztési összefoglaló |
||
23. sor:
===Minimális költségű él===
Ha a gráfban van egy egyértelmű legkisebb költségű él, akkor a gráf minimális költségű feszítő fáinak mindegyike tartalmazni fogja ezt az élt. Különben a vágásokra alkalmazott érveléssel kimutatható, hogy az adott feszítő fa nem minimális költségű.
==Algoritmusok==
A legismertebb feszítő fa algoritmusok a [[Kruskal-algoritmus]] és a [[Prim-algoritmus]]. Mindkettő mohón épít egy minimális feszítő fát. A Kruskal-algoritmus kezdetben az összes pontot tekinti, a Prim-algoritmus pedig egy kezdőpontot. Innen elindulva éleket hozzávéve készítik el a fát.
32 ⟶ 33 sor:
A számítógép-tudomány egyik legrégibb nyitott kérdése, hogy mi a lehető leggyorsabb minimális költségű feszítő fát adó algoritmus. Nyilván van egy lineáris alsó határ, mivel minden költséget meg kell vizsgálni. Ha az élsúlyok egészek, és egy adott korlát alatt vannak, akkor ismertek lineáris polinomiális algoritmusok.<ref>Fredman, M. L. and Willard, D. E. 1994. [http://dx.doi.org/10.1016/S0022-0000(05)80064-9 Trans-dichotomous algorithms for minimum spanning trees and shortest paths]. J. Comput. Syst. Sci. 48, 3 (Jun. 1994), 533–551.</ref> Általában, vannak véletlen algoritmusok, amik várható futási ideje lineáris.<ref>Karger, D. R., Klein, P. N., and Tarjan, R. E. 1995. [http://doi.acm.org/10.1145/201019.201022 A randomized linear-time algorithm to find minimum spanning trees]. J. ACM 42, 2 (Mar. 1995), 321–328.</ref><ref>Pettie, S. and Ramachandran, V. 2002. [http://portal.acm.org/citation.cfm?id=545381.545477&coll=GUIDE&dl=GUIDE&CFID=60207697&CFTOKEN=18906052 Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms]. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, January 06 - 08, 2002). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 713–722.</ref> De még mindig nyitott kérdés, hogy van-e lineáris idejű determinisztikus algoritmus általános élsúlyokra.<ref>Pettie, S. and Ramachandran, V. 2002. [http://portal.acm.org/citation.cfm?doid=505241.505243 An optimal minimum spanning tree algorithm]. J. ACM 49, 1 (Jan. 2002), 16–34.</ref>
A feladatot párhuzamosított algoritmussal is sikerült megoldani. Lineáris számú processzorral <math>O(\log n)</math> időben található egy minimális költségű feszítő fa.<ref>Chong, K. W., Han, Y., and Lam, T. W. 2001. [http://doi.acm.org/10.1145/375827.375847 Concurrent threads and optimal parallel minimum spanning trees algorithm]. J. ACM 48, 2 (Mar. 2001), 297–323.</ref><ref>Pettie, S. and Ramachandran, V. 2002. [http://dx.doi.org/10.1137/S0097539700371065 A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest]. SIAM J. Comput. 31, 6 (Jun. 2002), 1879–1895.</ref> David A. Bader és Guojing Cong egy 2003-as cikkükben közölt egy párhuzamosított algoritmust, ami 8 processzoron ötször gyorsabb, mint egy optimalizált szekvenciális algoritmus.<ref>Bader, D. A. and Cong, G. 2006. [http://dx.doi.org/10.1016/j.jpdc.2006.06.001 Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs]. J. Parallel Distrib. Comput. 66, 11 (Nov. 2006), 1366–1378.</ref> A Prim- és a Kruskal-algoritmus nem párhuzamosítható, ezért a párhuzamos algoritmusok a
Más speciális algoritmusok nagy, külső táron tárolt gráfokra alkalmasak. Kis gráfokon kétszer-ötször lassabbak, mint a hagyományos algoritmusok<ref>R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn. [http://citeseer.ist.psu.edu/dementiev04engineering.html Engineering an external memory minimum spanning tree algorithm]. In Proc. 3rd IFIP Intl. Conf. on Theoretical Computer Science, pages 195--208, 2004.</ref>
38 ⟶ 39 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 független azonos eloszlású valószínűségi változók, amelyek <math>F</math>eloszlásfüggvénye kielégíti az <math>F'(0) > 0</math> egyenlőtlenséget, igaz az az állítás, hogy 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.
83 ⟶ 85 sor:
|1,0979027
|}
==Lásd még==
* [[Gráf]]
| |||