h2. Introducere

Conectivitatea este una din problemele clasice in teoria grafurilor, avand multe aplicatii practice, iar gasirea unei taieturi minime intr-un graf cu costuri este fundamentala in algoritmica. Pentru a fi mai precisi, ea consta in partitionarea unui set de noduri in doua multimi nevide, astfel incat suma costurilor muchiilor dintre cele doua multimi sa fie minima. Metodele clasice de abordare a acestei probleme sunt in stransa legatura cu gasirea unui flux maxim intr-o retea de transport. Ford si Fulkerson [1956] au enuntat teorema flux maxim - taietura minima, care arata dualitatea dintre fluxul maxim al unei retele de transport si taietura minima ce poate fi facuta astfel incat sursa si destinatia retelei sa se afle in multimi diferite. Gasirea unei taieturi minime fara sa fie specificate 2 noduri care sa se afle in multimi diferite, se poate face fixand un nod sursa, iar destinatia luand pe rand toate valorile diferite de sursa, in final alegandu-se optimul.

Conectivitatea este una din problemele clasice in teoria grafurilor, avand multe aplicatii practice, iar gasirea unei taieturi minime intr-un graf cu costuri este fundamentala in algoritmica. Pentru a fi mai precisi, ea consta in partitionarea unui set de noduri in doua multimi nevide, astfel incat suma costurilor muchiilor dintre cele doua multimi sa fie minima. Metodele clasice de abordare a acestei probleme sunt in stransa legatura cu gasirea unui flux maxim intr-o retea de transport. Ford si Fulkerson [1956] au enuntat teorema flux maxim - taietura minima, care arata dualitatea dintre fluxul maxim al unei retele de transport si taietura minima ce poate fi facuta astfel incat sursa si destinatia retelei sa se afle in multimi diferite. Gasirea unei taieturi minime fara sa fie specificate 2 noduri care sa se afle in multimi diferite, se poate face fixand un nod sursa, iar destinatia luand pe rand toate valorile diferite de sursa, in final alegandu-se optimul. Algoritmul prezentat in acest articol insa nu se foloseste de nicio metoda care are legatura cu fluxul maxim.
 
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:
 
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}._
 
Teorema este adevarata deoarece facand o taietura minima in graf nodurile s si t fie vor fi in aceeasi multime (primul caz tratat), fie in multimi diferite (cel de-al doilea caz).
 
Asadar o procedura care gaseste o taietura minima _s-t arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.