Stoer-Vagnerov algoritam

Stoer-Vagnerov algoritam u teoriji grafova predstavlja rekurzivan algoritam koji rešava problem minimalnog reza u neusmerenom težinskom grafu. Predložen je od strane Frenka Vagnera (eng. Frank Wagner) i Methild Stoera (eng. Mechthild Stoer) 1995. godine. Suštinska ideja ovog algoritma je da suzi graf spajajući čvorove najveće težine, sve dok graf ne sadrži samo dva seta kombinovanih najviših čvorova^[2]. Nakon svakog suženja, težina spojenog reza se čuva u listi. Konačno rez najmanje težine u listi biće minimum grafa.

Rez predstavlja podelu čvorova grafa u dva nesrazmerna podskupa. Minimalan rez je rez čija veličina ili težina nije veća od veličine bilo kog drugog reza. Za težinski graf minimalan rez će jednostavno biti rez sa najmanjim brojem grana. Za težinski graf, zbir svih težina čvorova reza određuje da li je rez minimalan. U praksi, problem mimimalnog reza se uvek raspravlja zajedno sa problemom maksimalnog protoka jer prilikom traženja maksimalnog kapaciteta mreže minimalan rez je "usko grlo" u grafu ili mreži.

Stoer-Vagnerov algoritam minimalnog reza

Neka je $G$ $=$ ( $V,E,$ $\omega$ ) težinski neusmeren graf. Neka $(S,T)$ budu globalni minimalni rezovi grafa $G$ . Pretpostavimo da $s,t\in V$ .

Ako $|\{s,t\}\cap S|=1$ onda su $(S,T)$ očigledno $s-t$ minimalni rez grafa $G$ .^[3]

Ovaj algoritam počinje pronalaženjem $s-t$ minimalnog reza $(S,T)$ grafa $G$ dva temena $\{s,t\}$ $\in$ $V$ . Par $(S,T)$ ima dve različite mogućnosti, $(S,T)$ su minimalni rez grafa $G$ ili pripadaju istoj strani minimalnog reza grafa $G$ . Dakle minimalni rez se može pronaći proveraavanjem grafa $G/\{s,t\}$ koji nastaje nakon spajanja čvorova $s$ i $t$ . Tokom spajanja, ako su $s$ i $t$ tpovezani granom, ta grana nestaje . Ako su $s$ i $t$ povezani granom sa čvorom najveće težine onda težina čvora dobija novu vrednost $\omega (s,\upsilon )+\omega (t,\upsilon )$ .^[3] Algoritam se opisuje sa^[2]:

FazaMinimalnogReza $(G,w,a)$

    $A\gets \left\{a\right\}$ 
   while  $\ A\neq V$ 
       dodati u  $A$  najbliži čvor grafa
       smestiti rez-faze i smanjiti   $G$  spajanjem dva čvora koji su dodati poslednji

MinimalniRez $(G,w,a)$

   while  $|V|>1$ 
       FazaMinimalnogReza $(G,w,a)$ 
       if rez-faze je lakši od trenutnog minimalnog reza
           then postaviti rez-faze kao trenutni minimalni rez

Algoritam radi u fazama. U fazi FazaMinimalnogReza, podskup $A$ čvorova grafa raste počevši od nekog proizvoljnog čvora dok $A$ ne bude jednako $V$ . U svakom koraku, čvor koji je van skupa $A$ , ali je usko povezan sa skupom $A$ , dodaje se tom skupu. Ovaj postupak se formalno može pokazati kao^[2]: dodati čvor najveće težine $Z\not \in A$ tako da $\omega (A,Z)=max\{\omega (A,y)y\in A\}$ gde je $\omega (A,y)$ suma težina svih grana između $A:y$ . Stoga u samoj fazi par čvorova $s$ i $t$ kao i minimalan $s-t$ rez $C$ se utvrđuje.^[4] Nakon jedne faze FazaMinimalnogReza, dva čvora se spajaju u novi čvor, i grane ta dva čvora se zamenjuju novom granom čija je težina jednaka zbiru prethodne dve grane. A grane koje povezuju ove čvorove se uklanjaju. Ako postoji minimalan rez grafa $G$ odvajanjem $s$ i $t$ onda je $C$ minimalni rez grafa $G$ . Ako nije tako minimalan rez $C$ mora imati $s$ i $t$ na istoj strani. Stoga, algoritam ih spaja u jedan čvor. Pored toga MinimalniRez će se ažurirati nakon svake faze FazaMinimalnogReza. Nakon $n-1$ faza možemo odrediti minimalni rez.^[4]

Primer

Graf u koraku 1 prikazuje originalni graf $G$ i nasumično bira čvor 2 kao početni čvor za ovaj algoritam. U FazaMinimalnogReza, skup $A$ ima samo čvor 2, najteža ivica je ivica (2,3), tako da se čvor 3 dodaje u skup $A$ . Dalje, skup $A$ sadrži čvor 2 i čvor 3, najteža ivica je (3,4 ), pa se skupu $A$ dodaje čvor 4. Praćenjem ove procedure, poslednja dva čvora su čvor 5 i čvor 1, koji su s i t u ovoj fazi. Njihovim spajanjem, novi graf izgleda kao što je prikazano u koraku 2. U ovoj fazi, težina reza je 5, što je suma ivica (1,2) i (1,5). Sada, je završena prva petlja faze MinimalniRez.

U koraku 2, počevši od čvora 2, najteži ivica je (2,15), pa se čvor 15 stavlja u skup $A$ . Sledeća najteža ivica je (2,3) ili (15,6), biramo (15,6) pa se čvor 6 dodaje u skup. Onda uporedimo ivice (2,3) i (6,7) i izaberemo čvor 3 da bude stavljen u skup $A$ . Poslednja dva čvora su čvor 7 i čvor 8. Dakle, spojimo ivicu (7,8). Minimalan rez je 5, tako da minimum ostaje 5. Sledeći koraci ponavljaju iste operacije na spojeni graf, dok ne ostane samo jedna ivica na grafu, kao što je prikazano u koraku 7. Globalni minimalni rez ima ivicu (2, 3) i ivicu (6,7), što se uočava u koraku 5.

Dokaz korektnosti

Da bi se dokazala ispravnost ovog algoritma, moramo dokazati da je FazaMinimalnogReza u stvari najmanji $s{\text{-}}t$ rez grafa, gde su $s$ i $t$ dva čvora koja su poslednja dodata u fazi. Dakle, lema je prikazana ispod:

 Lema 1: FazaMinimalnogReza vraća minimalni  $s{\text{-}}t$ -rez grafa  $G$ .

Ovo dokazujemo indukcijom na skupu aktivnih temena. Neka je $C=(X,{\overline {X}})$ proizvoljan $s{\text{-}}t$ rez, i $CP$ rez faze. Moramo pokazati da je $W(C)\geq W(CP)$ . Primetimo da nam jedno izvršavanje faze FazaMinimalnogReza daje permutaciju svih temena u grafu (gde je $a$ prvi, a $s$ i $t$ su dva temena koja se dodaju poslednja u fazi). Dakle, mi kažemo da je čvor $v$ aktivan ako $v\in X$ , čvor pre čvora $v$ u redosledu temena proizvodenom fazom FazaMinimalnogReza je u ${\overline {X}}$ ili obrnuto, što će reći, da su na suprotnim stranama reza. Definišemo $A_{v}$ kao skup temena dodat u skup $A$ pre $v$ i $C_{v}$ kao rez od skupa $A_{v}\cup \{v\}$ izveden iz $C$ . Za sve aktivne čvorove $v$ :

$w(A_{v},v)\leq w(C_{v})$

Neka $v_{0}$ bude prvi aktivni čvor. Po definiciji sledi da su $w(A_{v_{0}},v_{0})$ and $w(C_{v_{0}})$ ekvivalentni. $A_{v_{0}}$ predstavlja sve čvorove dodate u $A$ pre $v_{0}$ , i ivice između tih čvorova i $v_{0}$ su ivice koje prelaze rez C. Dakle, kao što je prikazano gore, za aktivne čvorove $u$ i $v$ ( $v$ se dodaje u $A$ pre $u$ ):

$w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)$

$w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)$ uvođenjem , $w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})$

$w(A_{u},u)\leq w(C_{v})$ $w(A_{u}-A_{v},u)$ doprinosi $w(C_{u})$ ali ne $w(C_{v})$

Tako, pošto je $t$ uvek aktivni čvor posto poslednji rez faze odvaja $s$ od $t$ po definiciji, za bilo koji aktivni čvor $t$ :

$w(A_{t},t)\leq w(C_{t})=w(C)$

Dakle, maksimalna težina reza faze je jednaka $C$ .

Vremenska složenost

Vreme izvršavanja algoritma MinimalniRez je jednak vremenu izvršavanja faze FazaMinimalnogReza $|V|-1$ puta, koji se poziva na grafove sa smanjenjem broja čvorova i ivica. Za jedno izvršavanje faze FazaMinmalnogReza treba najviše $O(|E|+|V|\log |V|)$ vremena. Dakle, ukupno trajanje bi trebalo da bude proizvod dve faze kompleksnosti, koji je $O(|V||E|+|V|^{2}\log |V|)$ ^[2]. Za dalje poboljšanje, ključ je da se lako odabere sledeći čvor koji se dodaje u skup A, najbliži čvor. Tokom izvržavanja faze, svi čvorovi koji nisu u $A$ nalaze se u prioritetnom redu baziranom na osnovu ključne oblasti. Ključ čvora $V$ je zbir težina ivica koji ga spajaju sa trenutnim A, to jest, $w(A,v)$ . Kad god se čvor $v$ dodaje u $A$ mora da se izvrši ažuriranje reda. $v$ mora da bude izbrisan iz reda, a ključ svakog čvora $w$ koji se ne nalazi u $A$ , i koji je povezan sa $v$ mora se povećati za težinu ivice $vw$ , ako postoji. Pošto se ovo radi upravo jednom za svaku ivicu, ukupno moramo $|V|$ puta da izvršimo operaciju IzvuciMaksimum i $|E|$ puta operaciju PovećajKljuč. Korišćenjem Fibonačijevog hipa možemo izvršiti operaciju IzvuciMaksimum u $O(\log |V|)$ vremenu i operaciju PovećajKljuč u $O(1)$ vremenu. Tako, vreme potrebno za ovaj ključni korak koji dominira ostatakom faze, je $O(|E|+|V|\log |V|)$ .^[2]

Primer koda^[5]

// Implementacija Stoer-Vagnerovog algoritma preko matrice povezanosti
//
// Vreme izvršavanja:
// O(|V|^3)
//
// ULAZ:
// - graf, konstruisan korišćenjem DodajIvicu()
// IZLAZ:
// - (vrednost minimalnog reza, polovina čvorova u minimalnom rezu)
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int INF = 1000000000;

pair<int, VI> NadjiMinimalniRez(VVI &težine) {
  int N = težine.veličina();
  VI koriščen(N), rez, najbolji_rez;
  int najbolja_težina = -1;
  
  for (int faza = N-1; faza >= 0; faza--) {
    VI w = težine[0];
    VI dodati = korišćen;
    int prethodni, poslednji = 0;
    for (int i = 0; i < faza; i++) {
      prethodni = poslednji;
      poslednji = -1;
      for (int j = 1; j < N; j++)
	if (!dodati[j] && (poslednji == -1 || w[j] > w[poslednji])) poslednji = j;
      if (i == faza-1) {
	for (int j = 0; j < N; j++) težine[prethodni][j] += težine[poslednji][j];
	for (int j = 0; j < N; j++) težine[j][prethodni] = težine[prethodnji][j];
	korišćen[poslednji] = true;
	cut.push_back(poslednji);
	if (najbolja_težina == -1 || w[poslednji] < najbolja_težina) {
	 najbolji_rez = rez;
	 najbolja_težina = w[poslednji];
	}
      } else {
	for (int j = 0; j < N; j++)
	 w[j] += težine[poslednji][j];
	dodati[poslednji] = true;
      }
    }
  }
  return napravi_par(najbolja_težina, najbolji_rez);
}

const int maxn = 550;
const int inf = 1000000000;
int n, r;
int ivica[maxn][maxn], dist[maxn];
bool vis[maxn], bin[maxn];
void init()
{
    memset(ivica, 0, sizeof(ivica));  
    memset(bin, false, sizeof(bin));  
}
int contract( int &s, int &t ) // Naći s,t
{
    memset(dist, 0, sizeof(dist));  
    memset(vis, false, sizeof(vis));  
    int i, j, k, min_rez, maxc;  
    for(i = 1; i <= n; i++)  
    {  
        k = -1; maxc = -1;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j] && dist[j] > maxc)  
        {  
            k = j;  maxc = dist[j];  
        }  
        if(k == -1)return min_rez;  
        s = t;  t = k;  
        min_rez = maxc;  
        vis[k] = true;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j])  
            dist[j] += ivica[k][j];  
    }  
    return min_rez;  
}
int Stoer_Vagner()
{
    int min_rez, i, j, s, t, ans;  
    for(min_rez = inf, i = 1; i < n; i++)  
    {  
        ans = contract( s, t );  
        bin[t] = true;  
        if(min_rez > ans)min_rez = ans;  
        if(min_rez == 0)return 0;  
        for(j = 1; j <= n; j++)if(!bin[j])  
            ivica[s][j] = (ivica[j][s] += ivica[j][t]);  
    }  
    return min_rez;  
}

Reference

^ „Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1”. www.boost.org. Приступљено 7. 12. 2015.
^ ^а ^б ^в ^г ^д „Jednostavan algoritam minimalnog reza(eng. A Simple Min-Cut Algorithm)” (PDF).
^ ^а ^б „Beleške za Analizu algoritama: Globalni minimalni rezovi(eng. Lecture notes for Analysis of Algorithms: Global minimum cuts)” (PDF).
^ ^а ^б „Stoer-Vagnerov algoritam za minimalni rez(eng. The minimum cut algorithm of Stoer and Wagner)” (PDF).
^ „Stanford Univerzitet(Stanford University) Beleške ACM tima(ACM Team Notebook) (2014–15)”. web.stanford.edu. Приступљено 2015—12—07. Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)

Spoljašnje veze

Minimalni rez (primena u računarskim mrežama)

[1] „Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1”. www.boost.org. Приступљено 7. 12. 2015.

[dva-2] а ^б ^в ^г ^д „Jednostavan algoritam minimalnog reza(eng. A Simple Min-Cut Algorithm)” (PDF).

[tri-3] а ^б „Beleške za Analizu algoritama: Globalni minimalni rezovi(eng. Lecture notes for Analysis of Algorithms: Global minimum cuts)” (PDF).

[cetiri-4] а ^б „Stoer-Vagnerov algoritam za minimalni rez(eng. The minimum cut algorithm of Stoer and Wagner)” (PDF).

[5] „Stanford Univerzitet(Stanford University) Beleške ACM tima(ACM Team Notebook) (2014–15)”. web.stanford.edu. Приступљено 2015—12—07. Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)

[2]

[1]

[3]

[4]

[5]

Stoer-Vagnerov algoritam