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 taietura fazei. Cea mai mica dintre aceste taieturi ale fazei, reprezinta rezultatul dorit, si anume taietura minima in graf.

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 aduagat 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.

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$,

# 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)_ = α$

$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~})$

$α ≤ 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|)$}

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 - .campion 2006/2007, runda 07
* Terrorists - TopCoder, SRM 334, divizia I

* '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

3700