h2. Algoritm
Pe parcursul articolului, vom considera un graf neorientat G, multimea nodurilor o vom nota cu V, iar pe cea a muchiilor cu E. Fiecare muchie _e_ are un cost asociat _w(e)_. Observatia cheie pe care o putem face este ca daca stim cum sa gasim doua noduri _s_ si _t_, si valoarea taieturii minime _s-t_ (adica o taietura minima astfel incat s si t sa se afle in multimi diferite), aproape am rezolvat problema:
Pe parcursul articolului, vom considera un graf neorientat $G$, multimea nodurilor o vom nota cu $V$, iar pe cea a muchiilor cu $E$. Fiecare muchie $e$ are un cost asociat $w(e)$. Pentru a rezolva problema, vom cauta o modalitate cat mai simpla de a gasi 2 noduri $s$ si $t$, precum si valoarea taieturii minime $s-t$. Urmatoarea teorema ne explica de ce este necesar acest lucru:
Teorema 1: _Fie s si t doua noduri dintr-un graf G. Notam cu G/{s,t} graful obtinut din G prin fuzionarea nodurilor s si t. Atunci taietura minima a grafului G este cea mai mica dintre taietura minima s-t a grafului G si taietura minima a grafului G/{s,t}._
Teorema 1: _Fie $s$ si $t$ doua noduri dintr-un graf $G$. Notam cu $G/{s,t}$ graful obtinut din $G$ prin fuzionarea nodurilor $s$ si $t$. Atunci taietura minima a grafului $G$ este cea mai mica dintre taietura minima $s-t$ a grafului $G$ si taietura minima a grafului $G/{s,t}$._
Teorema este adevarata deoarece facand o taietura minima in graf nodurile s si t fie vor fi in aceeasi multime (primul caz tratat), fie in multimi diferite (cel de-al doilea caz).
Teorema este adevarata deoarece facand o taietura minima in graf nodurile $s$ si $t$ fie vor fi in multimi diferite (primul caz tratat), fie in aceeasi multime (cel de-al doilea caz).
Asadar o procedura care gaseste o taietura minima _s-t arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.
Asadar o procedura care gaseste o taietura minima _$s-t$ arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.
Urmatorul algorim, care poarta denumirea de _cautare maxima de adiacenta_ (in engleza _maximum adjacency search_
sau _maximum cardinality search_) gaseste taietura _s-t_ dorita:
Urmatorul algorim, care poarta denumirea de _cautare maxima de adiacenta_ (in engleza _maximum adjacency search_ sau _maximum cardinality search_) gaseste taietura _$s-t$_ dorita:
== code(c) |
FazaTaieturiiMinime(G, w, a)
A <- {a}
CatTimp A != V
while A != V
adauga in A nodul cel mai puternic conectat
retine taietura si micsoreaza graful G prin fuzionarea ultimelor doua noduri adaugate
==
Explicatie: O submultime A a lui V creste incepand cu un nod arbitrar pana cand A devine egala cu V. La fiecare pas, nodul care nu se afla in A, _cel mai puternic conectat_, este adaugat multimii. Intr-o formulare mai formala, putem spune ca adaugam nodul
Explicatie: O submultime $A$ a lui $V$ creste incepand cu un nod arbitrar pana cand $A$ devine egala cu $V$. La fiecare pas, nodul care nu se afla in $A$, _cel mai puternic conectat_, este adaugat multimii. Intr-o formulare mai formala, putem spune ca adaugam nodul
z ∉ A astfel incat _w(A, z)_ = max{_w(A, y)_|y ∉ A},
$z ∉ A astfel incat w(A, z) = max{w(A, y) | y ∉ A},$
unde _w(A, y)_ este suma costurilor muchiilor dintre nodul y si nodurile care apartin multimii A. La sfarsitul fiecarei astfel de faze, ultimele doua noduri adaugate fuzioneaza, ceea ce inseamna ca cele doua noduri sunt inlocuite de un nou nod, si orice muchii de la un nod ramas la cele doua noduri scoase sunt inlocuite de o noua muchie de cost egal cu suma costurilor precedentelor doua muchii. Muchiile intre cele doua noduri sunt eliminate. Taietura lui V ce separa ultimul nod adaugat de restul grafului se numeste taitura a fazei. Cea mai mica dintre aceste taiteuri ale fazei, reprezinta rezultatul dorit, si anume taietura minima in graf.
unde $w(A, y)$ este suma costurilor muchiilor dintre nodul $y$ si nodurile care apartin multimii $A$. La sfarsitul fiecarei astfel de faze, ultimele doua noduri adaugate fuzioneaza, ceea ce inseamna ca cele doua noduri sunt inlocuite de un nou nod, si orice muchii de la un nod ramas la cele doua noduri scoase sunt inlocuite de o noua muchie de cost egal cu suma costurilor precedentelor doua muchii. Muchiile intre cele doua noduri sunt eliminate. Taietura lui $V$ ce separa ultimul nod adaugat de restul grafului se numeste taietura fazei. Cea mai mica dintre aceste taieturi ale fazei, reprezinta rezultatul dorit, si anume taietura minima in graf.
== code(c) |
TaieturaMinima(G, w, a)
while |V| > 1
==
FazaTaieturiiMinime(G, w, a)
daca taietura fazei este mai mica decat taietura minima curenta
atunci actualizeaza taietura minima curenta
==
Observatie: Nodul $a$ ramane fixat pe parcursul intregului algoritm. Am putea sa il alegem insa in mod arbitrar la fiecare pas.
h2. Corectitudine
Pentru a demonstra corectitudinea algoritmului, trebuie mai intai sa demonstram urmatoarea lema:
Lema 1: _Fiecare taietura faza reprezinta o taietura minima $s-t$, unde $s$ si $t$ sunt ultimele 2 noduri adaugate in faza curenta._
Demonstratie: Procedura FazaTaieturiiMinime sorteaza nodurile grafului curent, incepand cu a si terminand cu $s$ si cu $t$, in functie de ordinea in care acestea au fost adaugate in multimea $A$. Vom analiza o taietura $C$ $s-t$ oarecare a grafului curent si vom demonstra ca are costul mai mare sau egal cu cel al taieturii faza.
Numim un nod $v ≠ a$ activ (in raport cu taietura $C$) daca $v$ si ultimul nod adaugat inainte de $v$ se afla in multimi diferite. Fie $w(C)$ costul taieturii $C, A{~v~}$ multimea nodurilor adaugate inaintea lui $v, C{~v~}$ taietura lui $A{~v~} ∪ v$ indusa de $C$, iar $w(C{~v~})$ costul taieturii induse.
Vom arata prin inductie ca pentru fiecare nod activ $v$,
$w(A{~v~}, v) ≤ w(C{~v~})$
# Pentru primul nod activ, propozitia de mai sus este adevarata deoarece avem egalitate.
# Presupunem adevarata propozitia pentru toate nodurile active adaugate inaintea unui nod activ $v$, si fie $u$ urmatorul nod activ ce urmeaza sa fie adaugat. Atunci avem:
$w(A{~u~}, u) = w(A{~v~}, u) + w(A{~u~}\A{~v~}, u) = α$
In continuare, avem $w(A{~v~}, u) ≤ w(A{~v~}, v)$, deoarece atunci cand a fost ales, nodul $v$ era mai puternic conectat decat $u$ in raport cu $A{~v~}$. Prin inductie avem $w(A{~v~}, v) ≤ w(C{~v~})$. Toate muchiile dintre $A{~u~}\A{~v~}$ si $u$ conecteaza multimi diferite ale taieturii $C$. Deci ele contribuie la $w(C{~u~})$, dar nu si la $w(C{~v~})$. Asadar:
$α ≤ w(C{~v~}) + w(A{~u~}\A{~v~}, u) ≤ w(C{~u~})$
Concluzie: Cum $t$ este tot timpul un nod activ in raport cu $C$, putem concluziona ca $w(A{~t~}, t) ≤ w(C{~t~})$, ceea ce demonstreaza ca orice taietura $s-t$ are costul cel putin la fel de mare ca taietura faza.
h2. Analiza complexitatii
In cadrul procedurii TaieturaMinima, vom apela procedura FazaTaieturiiMinime de $O(|V|)$ ori. Observam ca in cadrul acestei din urma proceduri, avem nevoie de o structura de date care sa poata efectua in mod eficient urmatoarele operatii: _extrage_cheia_maxima_ si _creste_valoarea_unei_chei_. Putem folosi un heap Fibonacci pentru a efecuta operatia _extrage_cheia_maxima_ in {$O(log |V|)$} amortizat, iar pentru _creste_valoarea_unei_chei_ in O(1) amortizat, obtinand astfel o complexitate finala de {$O(|V|*|E| + |V|^2^*log |V|)$}. Nu recomand insa implementarea unei asemenea structuri in conditii de concurs, un heap binar fiind suficient, obtinandu-se astfel o complexitate de {$O(|V|*|E|*log |V|)$}
h2. Probleme de taietura in concursurile de algoritmica
* 'Croco':problema/croco - .campion 2006/2007, runda 07
* 'Terrorists':http://www.topcoder.com/stat?c=problem_statement&pm=7246 - TopCoder, SRM 334, divizia I
* 'Sabotaj':problema/sabotaj - FMI No Stress 2010
