Minimális feszítőfa
A gráfelmélet számos problémáját nevezik minimális átfutófának. A gráfelméletben a fa az összes csúcsot úgy köti össze, hogy bármelyik csúcsból pontosan egy út vezet a fa bármelyik másik csúcsához. Ha a gráf több várost ábrázol, amelyeket utak kötnek össze, akkor úgy választhatunk ki néhány utat, hogy minden város minden más városból elérhető legyen, de egyik városból a másikba ne lehessen egynél több úton eljutni.
Egy gráfnak egynél több átívelő fája is lehet, ahogyan a városok közötti utak kiválasztásának is több módja lehet.
A legtöbbször a grafikonok súlyozottak; két város közötti minden egyes kapcsolatnak súlya van: lehet, hogy az adott úton való utazás valamennyibe kerül, vagy az egyik kapcsolat hosszabb, mint a másik, ami azt jelenti, hogy több időt vesz igénybe az adott kapcsolaton való utazás. A gráfelmélet nyelvén a kapcsolatokat éleknek nevezzük.
A minimálisan átfutó fa egy fa. Abban különbözik a többi fától, hogy az élekhez tartozó súlyok összegét minimalizálja. Attól függően, hogy milyen a gráf, egynél több minimális átfutófa is létezhet. Egy olyan gráfban, ahol minden élnek ugyanaz a súlya, minden fa egy minimálisan átfogó fa. Ha minden élnek különböző súlya van (azaz nincs két azonos súlyú él), akkor pontosan egy minimálisan átfogó fa létezik.
Egy sík gráf minimális feszítőfája. Minden él a súlyával van jelölve, amely itt nagyjából arányos a hosszával.
A minimálisan átfutó fa megtalálása
Egy első próbálkozás
Nagyon egyszerű lehet olyan algoritmust készíteni, amely felfedezi a minimális átfutófát:
MST(G,W) függvény: T = {} amíg T nem képez átfutófát: keressük meg a minimális súlyozott élt E-ben, amely biztonságos T számára T = T union {(u,v)} return TEbben az esetben a "biztonságos" azt jelenti, hogy az él bevonása nem képez ciklust a gráfban. A ciklus azt jelenti, hogy egy csúcsból indulunk, több más csúcsba utazunk, és a kiindulási ponton érünk vissza anélkül, hogy ugyanazt az élt kétszer használnánk.
Történelem
Otakar Borůvka cseh tudós 1926-ban fejlesztette ki az első ismert algoritmust a minimális átfutófa megtalálására. Azt a problémát akarta megoldani, hogy Morvaország hatékony villamosenergia-lefedettségét megtalálja. Ma ez az algoritmus Borůvka algoritmusa néven ismert. Két másik algoritmus ma már általánosan használatos. Az egyiket Vojtěch Jarník fejlesztette ki 1930-ban, és Robert Clay Prim 1957-ben ültette át a gyakorlatba. Edsger Wybe Dijkstra 1959-ben fedezte fel újra, és Prim algoritmusának nevezte el. A másik algoritmust Kruskal algoritmusának nevezik, és Joseph Kruskal 1956-ban pulzálta. Mindhárom algoritmus mohó, és polinomiális időben fut.
Az eddigi leggyorsabb minimum-spanning tree algoritmust Bernard Chazelle fejlesztette ki. Az algoritmus a soft heapon, egy közelítő prioritási soron alapul. Futási ideje O(m α(m,n)), ahol m az élek száma, n a csúcsok száma, α pedig az Ackermann-függvény klasszikus funkcionális inverze. Az α függvény rendkívül lassan növekszik, így minden gyakorlati szempontból 4-nél nem nagyobb konstansnak tekinthető; így Chazelle algoritmusa nagyon közel lineáris időt vesz igénybe.
Mi a lehető leggyorsabb algoritmus erre a problémára? Ez a számítástechnika egyik legrégebbi nyitott kérdése. Egyértelműen van egy lineáris alsó korlát, hiszen legalább az összes súlyt meg kell vizsgálnunk. Ha az élek súlyai egész számok, amelyeknek bithossza korlátos, akkor ismertek lineáris futási idejű determinisztikus algoritmusok. Általános súlyok esetén léteznek olyan randomizált algoritmusok, amelyek várható futási ideje lineáris.
A problémát elosztott módon is meg lehet közelíteni. Ha minden egyes csomópontot számítógépnek tekintünk, és egyetlen csomópont sem ismer semmit a saját összekötő kapcsolatain kívül, akkor is kiszámítható az elosztott minimális átfutófa.
Kérdések és válaszok
K: Mi az a minimális átfutófa a gráfelméletben?
V: A minimálisan áthidaló fa a gráfelméletben olyan fa, amely minimalizálja az élekhez kapcsolt összes súlyt.
K: Mi a fa a gráfelméletben?
V: A fa a gráfelméletben az összes csúcsot úgy köti össze, hogy a fa bármelyik csúcsából csak egy út vezet a fa bármelyik másik csúcsához.
K: Mi a célja az utak kiválasztásának egy városokat ábrázoló gráfelméleti forgatókönyvben?
V: Az utak kiválasztásának célja egy városokat ábrázoló gráfelméleti forgatókönyvben az, hogy minden város elérhető legyen minden más városból, de az egyik városból a másikba való eljutás legfeljebb egy lehetséges útvonalon történjen.
K: Lehet egy gráfnak egynél több átlós fája?
V: Igen, egy gráfnak egynél több átfutófája is lehet.
K: Mi a különbség a minimális átfutófa és más gráfelméleti fák között?
V: A minimálisan átfutó fa minimalizálja az élekhez tartozó összes súlyt, míg más fák nem rendelkeznek ezzel a tulajdonsággal.
K: Mik az élek a gráfelméletben?
V: Az élek a gráfelméletben két csúcs közötti kapcsolatok.
K: Létezhet-e egynél több minimális átfutófa egy gráfban, különböző súlyozott élekkel?
V: Igen, attól függően, hogy a gráf hogyan néz ki, egynél több minimális átfutófa is lehet.
