Pagini recente » Istoria paginii runda/mdaaaa | Clasament dupa rating | Diferente pentru preoni-2007/runda-3/solutii intre reviziile 25 si 26 | Clasament dupa rating | Diferente pentru taietura-minima intre reviziile 40 si 39
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.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.