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

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

        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.

Observatie: Nodul _a_ ramane fixat pe parcursul intregului algoritm. Am putea sa il alegem insa in mod arbitrar la fiecare pas.

h2. Corectitudine

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,