Kruskal-algoritmus
A Kruskal-algoritmus egy súlyozott gráfokat feldolgozó mohó algoritmus. Ha a gráf összefüggő, akkor minimális feszítőfa megalkotására szolgál, ha nem, akkor minimális feszítőerdőt hoz létre.
Az algoritmus lépései a következőek:
- Válasszuk ki a legkisebb súlyú élt.
- Amennyiben az él a részgráfhoz való hozzáadása kört alkot, dobjuk azt el.
- Ha van még nem vizsgált él, folytassuk az előző lépésekkel.
Az algoritmus Joseph Kruskal (1928–2010) amerikai matematikustól és informatikustól származik, aki 1956-ban írta le.
Az algoritmus leírása
Az éleket súlyuk szerint növekvő sorrendbe rendezzük, és sorra megvizsgáljuk, hogy melyeket vehetjük be a megoldásba. Annak ellenőrzése, hogy egy vizsgált él nem zár be kört, nagyon egyszerű. Kezdetben a gráf minden csúcsa egy-egy halmazt alkot. Egy vizsgált él akkor kerül be a megoldásba, ha a két végpontja két különböző halmazban van, és ekkor a két halmazt egyesítjük. Addig folytatjuk, amíg egy halmazt kapunk eredményül.
Példa:
![]() | Rendezzük súly szerinti növekvő sorrendbe a gráf éleit: {A,D}, {C,E}, {D,F}, {A,B}, {B,E}, {B,C}, {E,F}, {B,D}, {E,G}, {F,G}, {D,E} Kiinduló halmazok: {A}, {B}, {C}, {D}, {E}, {F}, {G} |
![]() | Az első él: {A,D}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,D}, {B}, {C}, {E}, {F}, {G} |
![]() | A következő él: {C,E}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,D}, {B}, {C,E}, {F}, {G} |
![]() | A következő él: {D,F}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,D,F}, {B}, {C,E}, {G} |
![]() | A következő él: {A,B}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,B,D,F}, {C,E}, {G} |
![]() | A következő él: {B,E}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,B,C,D,E,F}, {G} |
![]() | {B,C}, {E,F}, {B,D} egyike sem jöhet szóba, mert végpontjuk ugyanazon halmazban van, tehát kör zárulna be (az ábrán piros színnel vannak jelölve). A következő él {E,G}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,B,C,D,E,F,G} A zöld élek megadják a keresett feszítőfát. |
Alkalmazása
A Kruskal-algoritmus annak a tételnek az egyszerű bizonyítására készült, hogy a minimális költségű feszítőfa egyértelmű, ha a gráfban nincs két azonos súlyú él.
Bonyolultsága
Jelölje a következőkben a csúcsok számát n, az élek számát m! A futási idő magában foglalja az élek rendezését, és a gráf körmentességének vizsgálatát. A rendezés ideje . Jó implementálás esetén a körmentesség vizsgálata ennél gyorsabb, tehát a futási időt a rendezés határozza meg. Sűrű gráfokon a Prim-algoritmus gyorsabb.
Ha az élek eleve rendezettek, akkor a Kruskal-algoritmus gyorsabb. Ekkor csak a körmentesség vizsgálatát kell tekintetbe vennünk. A futási idő lerövidítése érdekében a csúcsokat egy alkalmas adatszerkezetben tároljuk:
Először is legyen
- ahol .
A partíció minden osztályához tartozik egy ri reprezentáns elem. Kezdetben minden csúcs egy külön osztályt alkot. Ebben az adatszerkezetben az egyes osztályokat különálló bináris fák tárolják, ahol minden él a szülő felé mutat, és a gyökérnek csak egy gyereke van. Ha tudni akarjuk, hogy egy csúcs melyik osztályba tartozik, akkor felmegyünk az éleken egészen a gyökérig, ahol a reprezentáns elem van. Ha egyesíteni akarunk két fát, akkor az alacsonyabb fát a magasabb csúcsa alá csatoljuk második gyerekként, majd innen emeljük ki az új reprezentáns elemet.
Ez az adatszerkezet tárolja, hogy mely csúcsok tartoznak össze. Ha v1v2 élt vizsgáljuk, akkor tudnunk kell, hogy v1 és v2 különböző osztályokba tartoznak-e. Ehhez megkeressük a reprezentáns elemeket. Ha különbözők, akkor v1v2 hozzáveendő a gráfhoz, és a két partíció egyesítendő. Ha nem ez a helyzet, akkor az él hozzávételével kör keletkezne, ezért ezt az élt kihagyjuk.
Összesen 2m-szer keresünk reprezentáns elemet, és n-1-szer egyesítünk. Az amortizációs bonyolultság[1] ahol praktikusan konstans, de a végtelenhez tartó függvény. Ezért nem hagyható ki az ordo jelölésből.
Helyessége
Legyen élköltséges összefüggő gráf, és legyen az algoritmus végeredménye. A korrektség belátásához a következőket kell bizonyítani:
- Az algoritmus véget ér, nem ciklizál
- F feszítőfa G-ben
- F feszítő részgráf
- F körmentes
- F összefüggő
- F minimális költségű
Az algoritmus terminál:
Az algoritmus minden élt egyszer vizsgál meg. Mivel a gráf véges, ezért véges sok élt tartalmaz, így az algoritmus véget ér.
F feszítő részgráf G-ben:
Mivel a csúcshalmaz ugyanaz, és F élei G élei közül kerülnek ki, ezért F feszítő részgráf G-ben.
F körmentes:
Mivel az algoritmus nem vesz hozzá a gráfhoz olyan élt, amivel kör keletkezhetne, ezért F körmentes.
F összefüggő:
Tegyük fel indirekt, hogy F nem összefüggő. Ekkor F-ben van egy x és egy y csúcs, ami között nincs út F-ben. Mivel G összefüggő, ezért G-ben van egy x-et és y-t összekötő út. Ezen az úton van egy egy él, ami összeköti F x-et és y-t tartalmazó komponenseit. jelölje ezt e!
Az algoritmus minden élt megvizsgál, tehát e-t is. Mivel x és y között nincs út, azért az e él bevételével nem keletkezik kör. Tehát e bekerül F-be. Ellentmondás.
F minimális a w költségfüggvényre nézve:
Ez egy általánosabb tételből adódik, ami szerint egy matroidon a mohó algoritmusok megtalálják a minimális költségű megoldást. Ez az állítás ettől függetlenül is belátható.:[2]
Tegyük fel indirekt, hogy van ellenpélda! Egy él esetén az algoritmus még korrekt, ezért a legkisebb élszámú ellenpélda több élt tartalmaz. Jelölje az algoritmus által generált feszítőfát F, és jelölje F1 azt minimális költségű feszítőfát, ami a lehető legtöbb élt tartalmazza F-ből!
Nyilván mindkét fa ugyanannyi élt tartalmaz. Az éleket költségük szerint növekvő sorrendbe rendezzük. Ekkor van egy minimális i index, amire F-ben drágább él van, mint F1-ben. Tekintjük az F0 részfát, amit az algoritmus az első i él átvizsgálása után ad. F0 tehát az {e1, e2, …, ei} éleket tartalmazza. Ekkor az F1 fában van egy f él, amit ki lehet cserélni ei-vel, amivel egy újabb fa keletkezik. Jelölje ezt a fát F1!
f vagy az i-edik él F1-ben, így könnyebb, mint ei, vagy f a j-edik él F1-ben, amire a rendezés miatt j < i. F1 tehát könnyebb, mint F0. Mivel azonban az algoritmus kisebb élszámokra jól működik, ezért F0=F, és i= |M|, és ei, az utolsó él nehezebb, mint f, F1 utolsó éle.
Tehát F1 élei az első ei élközül valók, és ez feszítőfa az első ei él alkotta részfában, míg az algoritmus erre a részgráfra az {e1, e2, …, ei} éleket adja. Mivel az algoritmus minden kisebb élszámra korrekt, ez egy feszítőfa, de F1 ennél eggyel több élt tartalmazza, így nem lehet feszítőfa. Ellentmondás.
Jegyzetek
Források
- Az adatstruktúra demonstrációja
- Korrektség[halott link]
Kapcsolódó szócikkek
- Gráf
- Fa (gráfelmélet)
- Minimális feszítőfa
- Prim-algoritmus
- Kruskal-tétel
Fordítás
- Ez a szócikk részben vagy egészben az Algorithmus von Kruskal című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Matematikaportál
Informatikai portál