Nu aveti permisiuni pentru a descarca fisierul grader_test5.ok
Diferente pentru taietura-minima intre reviziile #6 si #5
Nu exista diferente intre titluri.
Diferente intre continut:
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.
Urmatorul algorim, care poarta denumirea de _cautare maxima de adiacenta_ (in engleza _maximum adjacency search_
sau _maximum cardinality search_) gaseste taietura _s-t_ dorita:
== code(c) |
TaieturaMinima(G, w, a)
A <- {a}
CatTimp A != V
adaoga in A nodul cel mai puternic conectat
retine taietura si micsoreaza graful G prin fuzionarea ultimelor doua noduri adaogate
==
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 adogat multimii. Intr-o formulare mai formala, putem spune ca adaogam nodul
z
Asadar o procedura care gaseste o taietura minima _s-t arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.
