h1. Taietura minima in graf cu costuri

(Categoria _Grafuri_, Autor _Andrei Grigorean_)

(Categoria _Algoritmi_, Autor _Andrei Grigorean_)

Articolul de fata isi propune sa studieze problema gasirii unei taieturi minime intr-un graf neorientat cu costuri. Algoritmul prezentat este simplu atat ca implementare, cat si ca demonstrare a corectitudinii, iar timpul sau de executie este la fel de bun ca al oricarui algoritm cunoscut pana in momentul de fata.

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 binomial fiind suficient, obtiandu-se astfel o complexitate de {$O(|V|*|E|*log V)$}