Diferente pentru taietura-minima intre reviziile #39 si #46

Nu exista diferente intre titluri.

Diferente intre continut:

Explicatie: O submultime $A$ a lui $V$ creste incepand cu un nod arbitrar pana cand $A$ devine egala cu $V$. La fiecare pas, nodul care nu se afla in $A$, _cel mai puternic conectat_, este adaugat multimii. Intr-o formulare mai formala, putem spune ca adaugam nodul
$z ∉ A astfel incat _w(A, z)_ = max{_w(A, y)_|y ∉ A},$
$z ∉ A astfel incat w(A, z) = max{w(A, y) | y ∉ A},$
unde $w(A, y)$ este suma costurilor muchiilor dintre nodul $y$ si nodurile care apartin multimii $A$. La sfarsitul fiecarei astfel de faze, ultimele doua noduri adaugate fuzioneaza, ceea ce inseamna ca cele doua noduri sunt inlocuite de un nou nod, si orice muchii de la un nod ramas la cele doua noduri scoase sunt inlocuite de o noua muchie de cost egal cu suma costurilor precedentelor doua muchii. Muchiile intre cele doua noduri sunt eliminate. Taietura lui $V$ ce separa ultimul nod adaugat de restul grafului se numeste taietura fazei. Cea mai mica dintre aceste taieturi ale fazei, reprezinta rezultatul dorit, si anume taietura minima in graf.
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

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3700