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.

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.

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.

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ű.

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ű.

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.

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:

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

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