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)_. 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:

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

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 multimi diferite (primul caz tratat), fie in aceeasi multime (cel de-al doilea caz).