Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-03 15:33:33.
Revizia anterioară   Revizia următoare  

Taietura minima in graf cu costuri

(Categoria Grafuri, Autor Andrei Grigorean)

Articolul de fata isi propune sa studieze problema gasirii unei taieturi minime intr-un graf neorientat cu costuri. Algoritmul prezentat este simplu atat ca implementare, cat si ca demonstrare a corectitudinii, iar timpul sau de executie este la fel de bun ca al oricarui algoritm cunoscut pana in momentul de fata.

Introducere

Conectivitatea este una din problemele clasice in teoria grafurilor, avand multe aplicatii practice, iar gasirea unei taieturi minime intr-un graf cu costuri este fundamentala in algoritmica. Pentru a fi mai precisi, ea consta in partitionarea unui set de noduri in doua multimi nevide, astfel incat suma costurilor muchiilor dintre cele doua multimi sa fie minima. Metodele clasice de abordare a acestei probleme sunt in stransa legatura cu gasirea unui flux maxim intr-o retea de transport. Ford si Fulkerson [1956] au enuntat teorema flux maxim - taietura minima, care arata dualitatea dintre fluxul maxim al unei retele de transport si taietura minima ce poate fi facuta astfel incat sursa si destinatia retelei sa se afle in multimi diferite. Gasirea unei taieturi minime fara sa fie specificate 2 noduri care sa se afle in multimi diferite, se poate face fixand un nod sursa, iar destinatia luand pe rand toate valorile diferite de sursa, in final alegandu-se optimul. Algoritmul prezentat in acest articol insa nu se foloseste de nicio metoda care are legatura cu fluxul maxim.

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). Observatia cheie pe care o putem face este ca daca stim cum sa gasim doua noduri s si t, si valoarea taieturii minime s-t (adica o taietura minima astfel incat s si t sa se afle in multimi diferite), aproape am rezolvat problema:

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 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:

TaieturaMinima(G, w, a)
    A <- {a}
    CatTimp A != V
        adauga in A nodul cel mai puternic conectat
        retine taietura si micsoreaza graful G prin fuzionarea ultimelor doua noduri adaugate

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 adugat multimii. Intr-o formulare mai formala, putem spune ca adaugam nodul

  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 cele doua noduri la celealte noduri ramase sunt inlocuite de o noua muchie de cost egal cu suma costurilor precedentelor doua muchii.