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]

Graf sa dva presecanja. Tačkasta crvena linija seče tri grane grafa. Zelena isprekidana linija predstavlja minimalni rez grafa, presecajući samo dve grane.

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.

 
Uspešan prolazak kroz graf sa 10 čvorova koristeći Kargerovog algoritam. Minimalan broj rezova je 3.
   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  .

 
Izbori nasumičnih grana uz pomoć Kargerovog algoritmu korespondira sa izvršavanjem Kruskalovog algoritma u grafu sa granama nasumičnog ranga sve dok ne ostanu samo dve komponente.

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

уреди
 
10 ponavljanja procedure skraćivanja. Peto ponavljanje nalazi minilani rez veličine 3.

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( )}


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.

Референце

уреди
  1. ^ а б 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. 
  2. ^ 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. 
  3. ^ 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 .
  4. ^ 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.