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

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. Probleme de taietura in concursurile de algoritmica

* Croco - .campion 2006/2007, runda 07
* Terrorists - TopCoder, SRM 334, divizia I

* 'Croco':problema/croco - .campion 2006/2007, runda 07
* 'Terrorists':http://www.topcoder.com/stat?c=problem_statement&pm=7246 - TopCoder, SRM 334, divizia I
* 'Sabotaj':problema/sabotaj - FMI No Stress 2010

3700