Minimális feszítőfa

Egy minimális feszítőfa

A minimális költségű feszítőfa vagy minimális feszítőfa (angolul minimum spanning tree) egy összefüggő, irányítatlan gráfban található legkisebb élsúlyú feszítőfa. A feszítőfa egy olyan fa, ami a gráf összes csúcsát tartalmazza és élei az eredeti gráf élei közül valók. A minimális feszítőfa nem feltétlenül egyértelmű, de annak súlya igen. Egy gráf tetszőleges minimális feszítőfájának keresésére használható Kruskal és Prim algoritmusa.

Tulajdonságai

Multiplicitás

Ha egy gráfban minden él költsége különböző, akkor a feszítő fa egyértelmű. Ha vannak egyező súlyú élek, akkor ez már nem egyértelmű. Ha például a gráf összes élének költsége ugyanannyi, akkor a gráf összes feszítő fája minimális feszítő fa.

Az összes élsúly különbözősége esetére az egyértelműség indirekt úton bizonyítható:

Legyen T₁ és T₂ is minimális súlyú feszítő fa. T₁ és T₂ különbözőek, tehát van egy e¹ él T₁-ben, ami nincs T₂-ben, és T₂-ben egy e² él, ami nincs T₁-ben. Ekkor e²-t hozzávéve T₁-hez keletkezik egy kör. Ha most e¹ költsége kisebb, mint e²-é, akkor e¹-t kidobva egy kisebb súlyú feszítő fához jutunk, ami ellentmondás. Fordítva, ha e¹ költsége a nagyobb, szintén ellentmondáshoz jutunk a T₂ fához hozzávéve az e¹ élt, és kidobva e²-t.

Minimális költségű részgráf

Ha a költségek nem negatívak, akkor a minimális feszítő fa a minimális költségű összefüggő részgráf, mivel a körökből ki lehetne venni egy élt a részgráf szétesése nélkül.

Kapcsolata a gráf köreivel és vágásaival

Ha C kör a gráfban, akkor a legnagyobb költségű éle nem tartozik egy minimális költségű feszítő fához.

Ugyanis, ha egy feszítő fa tartalmazza ezt az élt, akkor elhagyva a fa két részfára esik szét. Ehhez hozzávéve a C kört a két rész újra összefüggővé válik. Innen elhagyva a legnehezebb élt is összefüggő marad, ezért van a körben egy kisebb költségű él, ami összekapcsolja a két részfát, és aminek kisebb a költsége, mint a legnehezebb élnek, ezzel a fa költsége csökkent.

Duálisan, ha C vágás, akkor a legkisebb költségű éle éle az összes minimális költségű feszítő fának.

Ugyanis, ha egy feszítő fában nincs benne ez az él, akkor hozzávéve keletkezik egy kör. Elhagyva a körnek azt a másik élét, ami éle C-nek is, a feszítő fa költsége csökken.

Ezek az állítások csak arra az esetre igazak, ha a kör, illetve a vágás élei között egyértelműen van legnagyobb, illetve legkisebb költségű.

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.

A fordított mohó algoritmus, másik nevén óvatos algoritmus éleket töröl, mégpedig minden körből törli a legnagyobb költségű élt. A vegyes algoritmus két oldalról közelíti a feszítő fát. Egyrészt épít egy erdőt, másrészt éleket töröl a körökből.

Ezek az algoritmusok mind polinomiális idejűek. A leggyorsabb minimális feszítő fa algoritmust Bernard Chazelle adta.^[1][2] Ennek futási ideje O(m α(m,n)), ahol m az élek száma, n jelöli a gráf pontjainak számát, és α az Ackermann-függvény inverze, ami olyan lassan nő, hogy gyakorlatilag konstansnak tekinthető.

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.^[3] Általában, vannak véletlen algoritmusok, amik várható futási ideje lineáris.^[4][5] De még mindig nyitott kérdés, hogy van-e lineáris idejű determinisztikus algoritmus általános élsúlyokra.^[6]

A feladatot párhuzamosított algoritmussal is sikerült megoldani. Lineáris számú processzorral ${\displaystyle O(\log n)}$ időben található egy minimális költségű feszítő fa.^[7][8] 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.^[9] A Prim- és a Kruskal-algoritmus nem párhuzamosítható, ezért a párhuzamos algoritmusok a Borůvka-algoritmuson alapulnak.

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^[10] Ezt írták: „A több merevlemezt megtöltő gráfok feszítő fáinak megtalálása egy teljes éjszakába telik egy PC-n.”

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 ${\displaystyle F}$ eloszlásfüggvénye kielégíti az ${\displaystyle F'(0)>0}$ 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 ${\displaystyle \zeta (3)/F'(0)}$-hoz, ahol ${\displaystyle \zeta }$ a Riemann-féle zéta-függvény.

Alan M. Frieze végesszó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álishatá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 ${\displaystyle [0,1]}$ intervallumon, egy minimális feszítőfa összsúlya:

Csúcsok száma	Az összköltség várható értéke	A várható érték közelí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

Kapcsolódó szócikkek

• Gráf
• Fa (gráfelmélet)
• Kruskal-algoritmus
• Prim-algoritmus

Források

1. Chazelle, B. 2000. A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47, 6 (Nov. 2000), 1028–1047.
2. Chazelle, B. 2000. The soft heap: an approximate priority queue with optimal error rate. J. ACM 47, 6 (Nov. 2000), 1012–1027.
3. Fredman, M. L. and Willard, D. E. 1994. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 3 (Jun. 1994), 533–551.
4. Karger, D. R., Klein, P. N., and Tarjan, R. E. 1995. A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42, 2 (Mar. 1995), 321–328.
5. Pettie, S. and Ramachandran, V. 2002. 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.
6. Pettie, S. and Ramachandran, V. 2002. An optimal minimum spanning tree algorithm. J. ACM 49, 1 (Jan. 2002), 16–34.
7. Chong, K. W., Han, Y., and Lam, T. W. 2001. Concurrent threads and optimal parallel minimum spanning trees algorithm. J. ACM 48, 2 (Mar. 2001), 297–323.
8. Pettie, S. and Ramachandran, V. 2002. A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. SIAM J. Comput. 31, 6 (Jun. 2002), 1879–1895.
9. Bader, D. A. and Cong, G. 2006. Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. J. Parallel Distrib. Comput. 66, 11 (Nov. 2006), 1366–1378.
10. R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn. Engineering an external memory minimum spanning tree algorithm Archiválva 2008. január 30-i dátummal a Wayback Machine-ben. In Proc. 3rd IFIP Intl. Conf. on Theoretical Computer Science, pages 195--208, 2004.

• Cormen – Leiserson – Rivest – Stein: Új algoritmusok, Scolar Kiadó, Bp., 2003. ISBN 9639193909
• Frank András: Operációkutatás