Стоер-Вагнеров алгоритам

Стоер-Вагнеров алгоритам у теорији графова представља рекурзиван алгоритам који решава проблем минималног реза у неусмереном тежинском графу. Предложен је од стране Френка Вагнера (енг. Франк Wагнер) и Метхилд Стоера (енг. Мецхтхилд Стоер) 1995. године. Суштинска идеја овог алгоритма је да сузи граф спајајући чворове највеће тежине, све док граф не садржи само два сета комбинованих највиших чворова^[2]. Након сваког сужења, тежина спојеног реза се чува у листи. Коначно рез најмање тежине у листи биће минимум графа.

Рез представља поделу чворова графа у два несразмерна подскупа. Минималан рез је рез чија величина или тежина није већа од величине било ког другог реза. За тежински граф минималан рез ће једноставно бити рез са најмањим бројем грана. За тежински граф, збир свих тежина чворова реза одређује да ли је рез минималан. У пракси, проблем мимималног реза се увек расправља заједно са проблемом максималног протока јер приликом тражења максималног капацитета мреже минималан рез је "уско грло" у графу или мрежи.

Стоер-Вагнеров алгоритам минималног реза уреди

Нека је $G$ $=$ ( $V,E,$ $\omega$ ) тежински неусмерен граф. Нека $(S,T)$ буду глобални минимални резови графа $G$ . Претпоставимо да $s,t\in V$ .

Ако $|\{s,t\}\cap S|=1$ онда су $(S,T)$ очигледно $s-t$ минимални рез графа $G$ .^[3]

Овај алгоритам почиње проналажењем $s-t$ минималног реза $(S,T)$ графа $G$ два темена $\{s,t\}$ $\in$ $V$ . Пар $(S,T)$ има две различите могућности, $(S,T)$ су минимални рез графа $G$ или припадају истој страни минималног реза графа $G$ . Дакле минимални рез се може пронаћи провераавањем графа $G/\{s,t\}$ који настаје након спајања чворова $s$ и $t$ . Током спајања, ако су $s$ и $t$ тповезани граном, та грана нестаје . Ако су $s$ и $t$ повезани граном са чвором највеће тежине онда тежина чвора добија нову вредност $\omega (s,\upsilon )+\omega (t,\upsilon )$ .^[3] Алгоритам се описује са^[2]:

ФазаМинималногРеза $(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

МинималниРез $(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

Алгоритам ради у фазама. У фази ФазаМинималногРеза, подскуп $A$ чворова графа расте почевши од неког произвољног чвора док $A$ не буде једнако $V$ . У сваком кораку, чвор који је ван скупа $A$ , али је уско повезан са скупом $A$ , додаје се том скупу. Овај поступак се формално може показати као^[2]: додати чвор највеће тежине $Z\not \in A$ тако да $\omega (A,Z)=max\{\omega (A,y)y\in A\}$ где је $\omega (A,y)$ сума тежина свих грана између $A:y$ . Стога у самој фази пар чворова $s$ и $t$ као и минималан $s-t$ рез $C$ се утврђује.^[4] Након једне фазе ФазаМинималногРеза, два чвора се спајају у нови чвор, и гране та два чвора се замењују новом граном чија је тежина једнака збиру претходне две гране. А гране које повезују ове чворове се уклањају. Ако постоји минималан рез графа $G$ одвајањем $s$ и $t$ онда је $C$ минимални рез графа $G$ . Ако није тако минималан рез $C$ мора имати $s$ и $t$ на истој страни. Стога, алгоритам их спаја у један чвор. Поред тога МинималниРез ће се ажурирати након сваке фазе ФазаМинималногРеза. Након $n-1$ фаза можемо одредити минимални рез.^[4]

Пример уреди

Граф у кораку 1 приказује оригинални граф $G$ и насумично бира чвор 2 као почетни чвор за овај алгоритам. У ФазаМинималногРеза, скуп $A$ има само чвор 2, најтежа ивица је ивица (2,3), тако да се чвор 3 додаје у скуп $A$ . Даље, скуп $A$ садржи чвор 2 и чвор 3, најтежа ивица је (3,4 ), па се скупу $A$ додаје чвор 4. Праћењем ове процедуре, последња два чвора су чвор 5 и чвор 1, који су с и т у овој фази. Њиховим спајањем, нови граф изгледа као што је приказано у кораку 2. У овој фази, тежина реза је 5, што је сума ивица (1,2) и (1,5). Сада, је завршена прва петља фазе МинималниРез.

У кораку 2, почевши од чвора 2, најтежи ивица је (2,15), па се чвор 15 ставља у скуп $A$ . Следећа најтежа ивица је (2,3) или (15,6), бирамо (15,6) па се чвор 6 додаје у скуп. Онда упоредимо ивице (2,3) и (6,7) и изаберемо чвор 3 да буде стављен у скуп $A$ . Последња два чвора су чвор 7 и чвор 8. Дакле, спојимо ивицу (7,8). Минималан рез је 5, тако да минимум остаје 5. Следећи кораци понављају исте операције на спојени граф, док не остане само једна ивица на графу, као што је приказано у кораку 7. Глобални минимални рез има ивицу (2, 3) и ивицу (6,7), што се уочава у кораку 5.

Доказ коректности уреди

Да би се доказала исправност овог алгоритма, морамо доказати да је ФазаМинималногРеза у ствари најмањи $s{\text{-}}t$ рез графа, где су $s$ и $t$ два чвора која су последња додата у фази. Дакле, лема је приказана испод:

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

Ово доказујемо индукцијом на скупу активних темена. Нека је $C=(X,{\overline {X}})$ произвољан $s{\text{-}}t$ рез, и $CP$ рез фазе. Морамо показати да је $W(C)\geq W(CP)$ . Приметимо да нам једно извршавање фазе ФазаМинималногРеза даје пермутацију свих темена у графу (где је $a$ први, а $s$ и $t$ су два темена која се додају последња у фази). Дакле, ми кажемо да је чвор $v$ активан ако $v\in X$ , чвор пре чвора $v$ у редоследу темена производеном фазом ФазаМинималногРеза је у ${\overline {X}}$ или обрнуто, што ће рећи, да су на супротним странама реза. Дефинишемо $A_{v}$ као скуп темена додат у скуп $A$ пре $v$ и $C_{v}$ као рез од скупа $A_{v}\cup \{v\}$ изведен из $C$ . За све активне чворове $v$ :

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

Нека $v_{0}$ буде први активни чвор. По дефиницији следи да су $w(A_{v_{0}},v_{0})$ анд $w(C_{v_{0}})$ еквивалентни. $A_{v_{0}}$ представља све чворове додате у $A$ пре $v_{0}$ , и ивице између тих чворова и $v_{0}$ су ивице које прелазе рез C. Дакле, као што је приказано горе, за активне чворове $u$ и $v$ ( $v$ се додаје у $A$ пре $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)$ увођењем , $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)$ доприноси $w(C_{u})$ али не $w(C_{v})$

Тако, пошто је $t$ увек активни чвор посто последњи рез фазе одваја $s$ од $t$ по дефиницији, за било који активни чвор $t$ :

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

Дакле, максимална тежина реза фазе је једнака $C$ .

Временска сложеност уреди

Време извршавања алгоритма МинималниРез је једнак времену извршавања фазе ФазаМинималногРеза $|V|-1$ пута, који се позива на графове са смањењем броја чворова и ивица. За једно извршавање фазе ФазаМинмалногРеза треба највише $O(|E|+|V|\log |V|)$ времена. Дакле, укупно трајање би требало да буде производ две фазе комплексности, који је $O(|V||E|+|V|^{2}\log |V|)$ ^[2]. За даље побољшање, кључ је да се лако одабере следећи чвор који се додаје у скуп А, најближи чвор. Током извржавања фазе, сви чворови који нису у $A$ налазе се у приоритетном реду базираном на основу кључне области. Кључ чвора $V$ је збир тежина ивица који га спајају са тренутним А, то јест, $w(A,v)$ . Кад год се чвор $v$ додаје у $A$ мора да се изврши ажурирање реда. $v$ мора да буде избрисан из реда, а кључ сваког чвора $w$ који се не налази у $A$ , и који је повезан са $v$ мора се повећати за тежину ивице $vw$ , ако постоји. Пошто се ово ради управо једном за сваку ивицу, укупно морамо $|V|$ пута да извршимо операцију ИзвуциМаксимум и $|E|$ пута операцију ПовећајКључ. Коришћењем Фибоначијевог хипа можемо извршити операцију ИзвуциМаксимум у $O(\log |V|)$ времену и операцију ПовећајКључ у $O(1)$ времену. Тако, време потребно за овај кључни корак који доминира остатаком фазе, је $O(|E|+|V|\log |V|)$ .^[2]

Пример кода^[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;  
}

Референце уреди

^ „Боост Грапх Либрарy: Стоер–Wагнер Мин-Цут - 1.46.1”. www.боост.орг. Приступљено 7. 12. 2015.
^ ^а ^б ^в ^г ^д „Једноставан алгоритам минималног реза(енг. А Симпле Мин-Цут Алгоритхм)” (ПДФ).
^ ^а ^б „Белешке за Анализу алгоритама: Глобални минимални резови(енг. Лецтуре нотес фор Аналyсис оф Алгоритхмс: Глобал минимум цутс)” (ПДФ).
^ ^а ^б „Стоер-Вагнеров алгоритам за минимални рез(енг. Тхе минимум цут алгоритхм оф Стоер анд Wагнер)” (ПДФ).
^ „Станфорд Универзитет(Станфорд Университy) Белешке АЦМ тима(АЦМ Теам Нотебоок) (2014–15)”. wеб.станфорд.еду. Приступљено 2015—12—07. Проверите вредност парамет(а)ра за датум: |аццесс-дате= (помоћ)

Спољашње везе уреди

Минимални рез (примена у рачунарским мрежама)

[1] „Боост Грапх Либрарy: Стоер–Wагнер Мин-Цут - 1.46.1”. www.боост.орг. Приступљено 7. 12. 2015.

[dva-2] а ^б ^в ^г ^д „Једноставан алгоритам минималног реза(енг. А Симпле Мин-Цут Алгоритхм)” (ПДФ).

[tri-3] а ^б „Белешке за Анализу алгоритама: Глобални минимални резови(енг. Лецтуре нотес фор Аналyсис оф Алгоритхмс: Глобал минимум цутс)” (ПДФ).

[cetiri-4] а ^б „Стоер-Вагнеров алгоритам за минимални рез(енг. Тхе минимум цут алгоритхм оф Стоер анд Wагнер)” (ПДФ).

[5] „Станфорд Универзитет(Станфорд Университy) Белешке АЦМ тима(АЦМ Теам Нотебоок) (2014–15)”. wеб.станфорд.еду. Приступљено 2015—12—07. Проверите вредност парамет(а)ра за датум: |аццесс-дате= (помоћ)

[2]

[1]

[3]

[4]

[5]

Стоер-Вагнеров алгоритам