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 ${\displaystyle (u,v)}$ u neorijentisanom grafu ${\displaystyle G=(V,E)}$. Neformalno govoreći, , skraćivanje broja grana spaja čvorove ${\displaystyle u}$ i ${\displaystyle v}$ u jedan, smanjujući ukupan broj čvorova u grafu za jedan. Sve ostale grane koje spajaju ${\displaystyle u}$ ili ${\displaystyle v}$ 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 ${\displaystyle (S,T)}$ u neorijentisanom grafu ${\displaystyle G=(V,E)}$ particioniše čvor ${\displaystyle V}$ u dva neprazna, razdvojena seta ${\displaystyle S\cup T=V}$. Isečak reza se sastoji od grana ${\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}$ 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,

${\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}$

Postoji ${\displaystyle 2^{|V|}}$ načina da se izabere za svaku najvišu tačku, bilo da pripada ${\displaystyle S}$ ili ${\displaystyle T}$, ali dva od ovih izbora čine ${\displaystyle S}$ ili ${\displaystyle T}$ praznim, i samim tim ne povećavaju broj rezova. Među preostalim izborima, zamenjivanjem uloga ${\displaystyle S}$ i ${\displaystyle T}$ se ne menja rez, tako da se svaki rez broji dva puta; stoga, postoji ${\displaystyle 2^{|V|-1}-1}$ 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 ${\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}$ težina reza predstavlja sumu težine grana izmedju čvorova u svakom delu

${\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}$

što se i slaže sa ne-težinskom definicijom za ${\displaystyle w=1}$.

Rez se ponekad naziva i “globalni rez” kako bi se razlikovao od “${\displaystyle s}$-${\displaystyle t}$ reza” za dati par temena, koji ima i dodatni zahtev(uslov) da ${\displaystyle s\in S}$ i ${\displaystyle t\in T}$. Svaki globalni rez je ${\displaystyle s}$-${\displaystyle t}$ rez za neke ${\displaystyle s,t\in V}$. Prema tome, problem minimalnog reza moze biti rešen u polinomijalnom vremenu tako što ćemo da iterišemo(označimo) sve slučajeve ${\displaystyle s,t\in V}$ i rešavajući rezultujući minimum ${\displaystyle s}$-${\displaystyle t}$ 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 ${\displaystyle O(mn+n^{2}\log n)}$.^[2]

Algoritam skraćivanja

Fundamentalna operacija Kargerovog algoritma je forma skraćivanja broja grana. Rezultat skraćivanja grane ${\displaystyle e=\{u,v\}}$ je novi čvor ${\displaystyle uv}$. Svaka grana ${\displaystyle \{w,u\}}$ ili ${\displaystyle \{w,v\}}$ za ${\displaystyle w\notin \{u,v\}}$ do krajnjih tačaka skraćene grane je zamenjena granom ${\displaystyle \{w,uv\}}$ do novog čvora. Konačno, skraćeni čvorovi ${\displaystyle u}$ i ${\displaystyle v}$ sa svim svojim starim granama su uklonjeni. Rezultujući graf ne sadrži petlje. Rezultat skraćene grane ${\displaystyle e}$ se označava kao ${\displaystyle G/e}$.

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(${\displaystyle G=(V,E)}$):
   dok ${\displaystyle |V|>2}$
       izaberi ${\displaystyle e\in E}$ nasumično ravnomerno
       ${\displaystyle G\leftarrow G/e}$
   vrati jedini rez iz ${\displaystyle G}$ 

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 ${\displaystyle O(|V|^{2})}$. Alternativno, procedura može biti pregledana uz pomoć Kruskalovog algoritma za konsturisanje minimalnog razapinjućeg stabla gde su grane težine ${\displaystyle w(e_{i})=\pi (i)}$ na osnovu nasumične permutacije ${\displaystyle \pi }$. 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 ${\displaystyle O(|E|\log |E|)}$.

Najbolja poznata implementacija je ${\displaystyle O(|E|)}$ vremenske i prostorne složenosti, ili u ${\displaystyle O(|E|\log |E|)}$ vremenu i ${\displaystyle O(|V|)}$ prostoru.^[1]

Verovatnoća uspešnosti algoritma za skraćivanje

U grafu ${\displaystyle G=(V,E)}$ sa ${\displaystyle n=|V|}$ čvorova, algoritam skraćivanja vraća minimalan rez sa polinomijalno malom verovatnoćom ${\displaystyle {\binom {n}{2}}^{-1}}$. Svaki graf ima ${\displaystyle 2^{n-1}-1}$ rezova,^[3] među kojima najviše može biti ${\displaystyle {\tbinom {n}{2}}}$ minimalnih rezova. Stoga, verovatnoća uspešnosti ovog algoritma je mnogo bolja od verovatnoće odabiranja reza nasumično, što je najviše ${\displaystyle {\tbinom {n}{2}}/(2^{n-1}-1)}$

Na primer, ciklični graf sa ${\displaystyle n}$ čvorova ima tačno ${\displaystyle {\binom {n}{2}}}$ 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 ${\displaystyle C}$ bude oznaka za ivice odredjenog minimalnog reza veličine ${\displaystyle k}$. Algoritam skraćivanja vraća ${\displaystyle C}$ ako nijedna od nasumičnih grana ne pripada isečku od ${\displaystyle C}$. U stvari, skraćivanje prve ivice izbegava ${\displaystyle C}$, a to se događa sa verovatnoćom ${\displaystyle 1-k/|E|}$. Minimalni stepen ${\displaystyle G}$ je najmanje ${\displaystyle k}$ (u suprotnom najviša tačka najmanjeg stepena bi indicirala manji rez), tako da je ${\displaystyle |E|\geq nk/2}$. Stoga, verovatnoća da algoritam skraćivanja izabere granu iz ${\displaystyle C}$ je

${\displaystyle {\frac {k}{|E|}}\leq {\frac {k}{nk/2}}={\frac {2}{n}}.}$

Verovatnoća ${\displaystyle p_{n}}$ da algoritam skraćivanja na ${\displaystyle n}$-čvorni graf izbegne ${\displaystyle C}$ zadovoljava rekurentnu jednačinu ${\displaystyle p_{n}\geq {\bigl (}1-{\frac {2}{n}}{\bigr )}p_{n-1}}$, sa ${\displaystyle p_{2}=1}$, što se može proširiti

${\displaystyle p_{n}\geq \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\prod _{i=0}^{n-3}{\frac {n-i-2}{n-i}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}={\binom {n}{2}}^{-1}\,.}$

Ponavljanje algoritma skraćivanja

Ponavljanjem algoritma skraćivanja ${\displaystyle T={\binom {n}{2}}\ln n}$ puta sa nezavisnim nasumičnim izborima i vraćanjem najmanjeg reza, verovatnoća da se ne nađe minimalan rez je

${\displaystyle {\Bigl [}1-{\binom {n}{2}}^{-1}{\Bigr ]}^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.}$

Ukupno vreme odradjivanja za ${\displaystyle T}$ ponavljanja za graf sa ${\displaystyle n}$ čvorova i ${\displaystyle m}$ grana je ${\displaystyle O(Tm)=O(n^{2}m\log n)}$.

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 ${\displaystyle t}$ čvorova.

   procedura skraćivanje(${\displaystyle G=(V,E)}$, ${\displaystyle t}$):
   dok ${\displaystyle |V|>t}$
       izaberi${\displaystyle e\in E}$ nasumično ravnomerno
       ${\displaystyle G\leftarrow G/e}$
   vrati ${\displaystyle G}$

Verovatnoća ${\displaystyle p_{n,t}}$ da ova procedura skraćivanja izbegne određen rez ${\displaystyle C}$ u ${\displaystyle n}$-čvornom grafu je

${\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}$

Ovaj izraz je ${\displaystyle \Omega (t^{2}/n^{2})}$ i postaje manji nego od ${\displaystyle {\frac {1}{2}}}$ oko ${\displaystyle t=\lceil 1+n/{\sqrt {2}}\rceil }$. Verovatnoća da je grana iz ${\displaystyle C}$ 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(${\displaystyle G=(V,E)}$):
   ako ${\displaystyle |V|<6}$:
       vrati minrez(${\displaystyle V}$)
   u suprotnom:
       ${\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }$
       ${\displaystyle G_{1}\leftarrow }$ skrati(${\displaystyle G}$, ${\displaystyle t}$)
       ${\displaystyle G_{2}\leftarrow }$ skrati(${\displaystyle G}$, ${\displaystyle t}$)
       vrati min {brziminrez(${\displaystyle G_{1}}$), brziminrez(${\displaystyle G_{2}}$)}

Analiza

Verovatnoća ${\displaystyle P(n)}$ da će algoritam pronaći određeni isečak ${\displaystyle C}$ je zadata rekurentnom relacijom

${\displaystyle P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}}$

sa rešenjem ${\displaystyle P(n)=O\left({\frac {1}{\log n}}\right)}$. Vreme trajanje(izvršavanja) funckije brziminrez zadovoljava

${\displaystyle T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}$

sa rešenjem ${\displaystyle T(n)=O(n^{2}\log n)}$. Kako bi se dostigla verovatnoća greške ${\displaystyle O(1/n)}$, algoritam može biti ponavljan ${\displaystyle O(\log n/P(n))}$ puta, za sveukupno vreme ${\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}$. 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 ${\displaystyle O(n^{2}\ln ^{3}n)}$.

Dokaz: Pošto znamo da je ${\displaystyle P(n)=O\left({\frac {1}{\ln n}}\right)}$, stoga nakon izvršavanja ovog algoritma${\displaystyle O(\ln ^{2}n)}$ puta, verovatnoća da se minimalni rez ne pronađe je

${\displaystyle \Pr[{\text{neuspelo nalaženje odredjenog min-reza}}]=(1-P(n))^{O(\ln ^{2}n)}\leq \left(1-{\frac {c}{\ln n}}\right)^{\frac {3\ln ^{2}n}{c}}\leq e^{-3\ln n}={\frac {1}{n^{3}}}}$.

Postoji najmanje ${\displaystyle {\binom {n}{2}}}$ minimalnih rezova, otuda je verovatnoća za ne-nalaženje bilo kog minimalnog reza

${\displaystyle \Pr[{\text{neuspelo nalaženje bilo kog min-reza}}]\leq {\binom {n}{2}}\cdot {\frac {1}{n^{3}}}=O\left({\frac {1}{n}}\right).}$

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 ${\displaystyle O(n^{2})}$ vremenu u gustom grafu. Karger-Štajnov algoritam za određivanje minimalnog reza se izvršava u ${\displaystyle O(n^{2}\ln ^{O(1)}n)}$ vremenu, što je približno gore navedenom.

Референце