Kargerov algoritam
U informatici i teoriji grafova, Kargerov algoritam je algoritam nasumične metode koji određuje minimalan rez povezanog grafa. Izmislio ga je Dejvid Karger i prvi put objavio 1993.[1]
Ideja algoritma je bazirana na konceptu skraćivanja grana u neorijentisanom grafu . Neformalno govoreći, , skraćivanje broja grana spaja čvorove i u jedan, smanjujući ukupan broj čvorova u grafu za jedan. Sve ostale grane koje spajaju ili su "ponovo nakačene" za spojeni čvor, efektivno stvarajući multigraf. Kargerov osnovni algoritam iterativno skraćuje nasumično odabrane grane sve dok ne ostanu samo dva čvora; ti čvorovi predstavljaju rez u originalnom grafu. Ponavljajući ovaj osnovni algoritam dovoljan broj puta nalazimo, uz veliku verovatnoću, minimalni rez.
Globalni problem minimalnog reza
уредиRez u neorijentisanom grafu particioniše čvor u dva neprazna, razdvojena seta . Isečak reza se sastoji od grana koje se nalaze između dva dela. Veličina (ili težina) reza u ne-težinskom grafu je kardinalnost isečka, npr., broj grana izmedju dva dela,
Postoji načina da se izabere za svaku najvišu tačku, bilo da pripada ili , ali dva od ovih izbora čine ili praznim, i samim tim ne povećavaju broj rezova. Među preostalim izborima, zamenjivanjem uloga i se ne menja rez, tako da se svaki rez broji dva puta; stoga, postoji različitih rezova. Problem minimalnog reza je da nađe rez najmanje veličine od ovih rezova.
Za težinske grafove sa granama pozitivne težine težina reza predstavlja sumu težine grana izmedju čvorova u svakom delu
što se i slaže sa ne-težinskom definicijom za .
Rez se ponekad naziva i “globalni rez” kako bi se razlikovao od “ - reza” za dati par temena, koji ima i dodatni zahtev(uslov) da i . Svaki globalni rez je - rez za neke . Prema tome, problem minimalnog reza moze biti rešen u polinomijalnom vremenu tako što ćemo da iterišemo(označimo) sve slučajeve i rešavajući rezultujući minimum - problema reza koristeći teoremu o maksimalnom protoku-minimalnom rezu i algoritam polinomijalnog vremena za maksimalni protok, kao što je Ford-Fulkersonov algoritam, iako ovaj pristup nije preporučljiv (optimalan). Postoji deterministički algoritam za globalni problem minimalnog reza koji se izvršava u vremenu .[2]
Algoritam skraćivanja
уредиFundamentalna operacija Kargerovog algoritma je forma skraćivanja broja grana. Rezultat skraćivanja grane je novi čvor . Svaka grana ili za do krajnjih tačaka skraćene grane je zamenjena granom do novog čvora. Konačno, skraćeni čvorovi i sa svim svojim starim granama su uklonjeni. Rezultujući graf ne sadrži petlje. Rezultat skraćene grane se označava kao .
Algoritam skraćivanja iznova i iznova smanjuje nasumično izabrane grane grafa sve dok ne ostanu samo dva čvora, a u tom trenutku postoji samo jedan rez.
procedura skraćivanje( ): dok izaberi nasumično ravnomerno vrati jedini rez iz
Kada je graf predstavljen listom susedstva ili matricom povezanosti, operacija skraćivanja jedne grane može biti implementirana linearnim brojem ažuriranja glavne strukture, uz ukupno vreme izvršavanja . Alternativno, procedura može biti pregledana uz pomoć Kruskalovog algoritma za konsturisanje minimalnog razapinjućeg stabla gde su grane težine na osnovu nasumične permutacije . Uklanjanjem najteže grane ovog stabla se dobijaju dve komponente koje opisuju rez. Na ovaj način, procedura skraćivanja može biti implementirana uz pomoć Kruskalovog algoritma u vremenu .
Najbolja poznata implementacija je vremenske i prostorne složenosti, ili u vremenu i prostoru.[1]
Verovatnoća uspešnosti algoritma za skraćivanje
уредиU grafu sa čvorova, algoritam skraćivanja vraća minimalan rez sa polinomijalno malom verovatnoćom . Svaki graf ima rezova,[3] među kojima najviše može biti minimalnih rezova. Stoga, verovatnoća uspešnosti ovog algoritma je mnogo bolja od verovatnoće odabiranja reza nasumično, što je najviše
Na primer, ciklični graf sa čvorova ima tačno minimalnih rezova, gledavši na svaki izbor od po 2 grane. Procedura skraćivanja nalazi svaku od navedenih sa jednakom verovatnoćom.
Kako bi generalno postavili verovatnoću uspešnosti, neka bude oznaka za ivice odredjenog minimalnog reza veličine . Algoritam skraćivanja vraća ako nijedna od nasumičnih grana ne pripada isečku od . U stvari, skraćivanje prve ivice izbegava , a to se događa sa verovatnoćom . Minimalni stepen je najmanje (u suprotnom najviša tačka najmanjeg stepena bi indicirala manji rez), tako da je . Stoga, verovatnoća da algoritam skraćivanja izabere granu iz je
Verovatnoća da algoritam skraćivanja na -čvorni graf izbegne zadovoljava rekurentnu jednačinu , sa , što se može proširiti
Ponavljanje algoritma skraćivanja
уредиPonavljanjem algoritma skraćivanja puta sa nezavisnim nasumičnim izborima i vraćanjem najmanjeg reza, verovatnoća da se ne nađe minimalan rez je
Ukupno vreme odradjivanja za ponavljanja za graf sa čvorova i grana je .
Karger-Štajnov algoritam
уредиNastavak (produžetak) Kargerovog algoritma usled David Karger i Clifford Stein dostiže unapređenje za nivo više.[4]
Osnovna ideja je da se izvršava procedura skraćivanja sve dok graf ne dostigne čvorova.
procedura skraćivanje( , ): dok izaberi nasumično ravnomerno vrati
Verovatnoća da ova procedura skraćivanja izbegne određen rez u -čvornom grafu je
Ovaj izraz je i postaje manji nego od oko . Verovatnoća da je grana iz skraćena raste kako se približava kraju. Ovo motiviše ideju prebacivanja na sporiji algoritam posle određenog broja skraćivanja (koraka skraćivanja).
procedura brziminrez( ): ako : vrati minrez( ) u suprotnom: skrati( , ) skrati( , ) vrati min {brziminrez( ), brziminrez( )}
Analiza
уредиVerovatnoća da će algoritam pronaći određeni isečak je zadata rekurentnom relacijom
sa rešenjem . Vreme trajanje(izvršavanja) funckije brziminrez zadovoljava
sa rešenjem . Kako bi se dostigla verovatnoća greške , algoritam može biti ponavljan puta, za sveukupno vreme . Ovo je unapredjenje u odnosu na Kargerov originalni algoritam.
Pronalaženje svih minimalnih rezova
уредиTeorema: Sa velikom verovatnoćom možemo naći sve minimalne rezove u vremenu .
Dokaz: Pošto znamo da je , stoga nakon izvršavanja ovog algoritma puta, verovatnoća da se minimalni rez ne pronađe je
- .
Postoji najmanje minimalnih rezova, otuda je verovatnoća za ne-nalaženje bilo kog minimalnog reza
Verovatnoća za neuspeh u pronalaženju je izuzetno mala kada je n dovoljno veliko.∎
Poboljšanje
уредиKako bi se odredio minimalni rez mora se proći kroz sve grane grafa bar jednom, što se obavlja za u vremenu u gustom grafu. Karger-Štajnov algoritam za određivanje minimalnog reza se izvršava u vremenu, što je približno gore navedenom.
Референце
уреди- ^ а б Karger, Dejvid (1993). „Globalni minimalni rezovi u RNC-u i Other Posledice Jednostavnog Algoritma Za Minamalne Rezove”. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms.
- ^ Stoer, Mechthild; Wagner, Frank (1997). „A simple min-cut algorithm”. Journal of the ACM. 44 (4): 585—591. S2CID 15220291. doi:10.1145/263867.263872.
- ^ Patrignani, Maurizio; Pizzonia, Maurizio (2001), „The complexity of the matching-cut problem”, Ур.: Brandstädt, Andreas; Le, Van Bang, Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14ÔÇô16, 2001, Proceedings, Lecture Notes in Computer Science, 2204, Berlin: Springer, стр. 284—295, MR 1905640, doi:10.1007/3-540-45477-2_26.
- ^ Karger, David R.; Stein, Clifford (1996). „A new approach to the minimum cut problem”. Journal of the ACM. 43 (4): 601—640. S2CID 5385337. doi:10.1145/234533.234534.