_w(A{~v~}, v) ≤ w(C{~v~})_

# Pentru primul nod activ, propizitia de mai sus este adevarata deoarece avem egalitate.

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

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

* Croco - .campion 2006/2007, runda 07

* Terrorists - TopCoder, SRM 334, divizia I