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 ${\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 r_i 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 v₁v₂ élt vizsgáljuk, akkor tudnunk kell, hogy v₁ és v₂ különböző osztályokba tartoznak-e. Ehhez megkeressük a reprezentáns elemeket. Ha különbözők, akkor v₁v₂ 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}}}\leq 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

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:

Az algoritmus véget ér, nem ciklizál
F feszítőfa G-ben
1. F feszítő részgrá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ő 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 F¹ 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 F¹-ben. Tekintjük az F₀ részfát, amit az algoritmus az első i él átvizsgálása után ad. F⁰ tehát az {e₁, e₂, …, e_i} éleket tartalmazza. Ekkor az F¹ fában van egy f él, amit ki lehet cserélni e_i-vel, amivel egy újabb fa keletkezik. Jelölje ezt a fát F₁!

f vagy az i-edik él F¹-ben, így könnyebb, mint e_i, vagy f a j-edik él F¹-ben, amire a rendezés miatt j < i. F₁ tehát könnyebb, mint F₀. Mivel azonban az algoritmus kisebb élszámokra jól működik, ezért F₀=F, és i= |M|, és e_i, az utolsó él nehezebb, mint f, F¹ utolsó éle.

Tehát F¹ élei az első e_i élközül valók, és ez feszítőfa az első e_i él alkotta részfában, míg az algoritmus erre a részgráfra az {e₁, e₂, …, e_i} éleket adja. Mivel az algoritmus minden kisebb élszámra korrekt, ez egy feszítőfa, de F¹ ennél eggyel több élt tartalmazza, így nem lehet feszítőfa. Ellentmondás.

Jegyzetek

↑ Theoretische Informatik III jegyzet. [2007. szeptember 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. szeptember 26.)
↑ Hubertus Th. Jongen: Optimierung B. Előadásjegyzet Aachen: Verlag der Augustinus-Buchhandlung, ISBN 3-925038-19-1

Források

Kapcsolódó szócikkek

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

[1] Theoretische Informatik III jegyzet. [2007. szeptember 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. szeptember 26.)

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

[1]

[2]