Kruskal-algoritmus

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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:

Prim Algorithm 0.svg 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}

Kruskal Algorithm 1.svg 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}

Kruskal Algorithm 2.svg 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}

Kruskal Algorithm 3.svg 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}

Kruskal Algorithm 4.svg 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}

Kruskal Algorithm 5.svg 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}

Kruskal Algorithm 6.svg {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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 \mathcal{O}(m\log m). 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

V = X_0 \uplus X_1 \uplus X_2 \uplus \ldots \uplus X_k ahol X_i \cap X_j = \varnothing \quad\forall i, j \in \lbrace 0, 1, \ldots, k \rbrace, i \neq j.

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] \mathcal{O}(m \cdot \log^* n) ahol \log^*(n)=\min \Bigl\{s\in\mathbb{N} \mid \underbrace{\log\bigl(\log(\ldots\log(n)\ldots)\bigr)}_{s-\text{mal}} \le 1 \Bigr\} praktikusan konstans, de a végtelenhez tartó függvény. Ezért nem hagyható ki az ordo jelölésből.

Helyessége[szerkesztés | forrásszöveg szerkesztése]

Legyen G = (V,E,w) élköltséges összefüggő gráf, és legyen F = (V,E') az algoritmus végeredménye. A korrektség belátásához a következőket kell bizonyítani:

  1. Az algoritmus véget ér, nem ciklizál
  2. F feszítő fa G-ben
    1. F feszítő gráf
    2. F körmentes
    3. F összefüggő
    4. 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ő gráf G-ben:

Mivel a csúcshalmaz ugyanaz, és F élei G élei közül kerülnek ki, ezért F feszítő grá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.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Theoretische Informatik III jegyzet
  2. Hubertus Th. Jongen: Optimierung B. Előadásjegyzet Aachen: Verlag der Augustinus-Buchhandlung, ISBN 3-925038-19-1

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]

Gráfalgoritmusok animációja

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.