== code(c) |
FazaTaieturiiMinime(G, w, a)
    A <- {a}

    while 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
==

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.

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

Vom arata prin inductie ca pentru fiecare nod activ v,

Vom arata prin inductie ca pentru fiecare nod activ _v_,

    _w(A{~v~}, v) ≤ w(C{~v~})_
# Pentru primul nod activ, propizitia 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:

# 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:

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.

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 binomial fiind suficient, obtiandu-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 binomial 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