Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-02-20 01:23:25.
Revizia anterioară   Revizia următoare  

Taietura minima in graf cu costuri

(Categoria Algoritmi, 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). Pentru a rezolva problema, vom cauta o modalitate cat mai simpla de a gasi 2 noduri s si t, precum si valoarea taieturii minime s-t. Urmatoarea teorema ne explica de ce este necesar acest lucru:

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 multimi diferite (primul caz tratat), fie in aceeasi multime (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:

FazaTaieturiiMinime(G, w, a)
    A <- {a}
    while 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 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},

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.

TaieturaMinima(G, w, a)
    while |V| > 1
        FazaTaieturiiMinime(G, w, a)
        daca taietura fazei este mai mica decat taietura minima curenta
            atunci actualizeaza taietura minima curenta

Observatie: Nodul a ramane fixat pe parcursul intregului algoritm. Am putea sa il alegem insa in mod arbitrar la fiecare pas.

Corectitudine

Pentru a demonstra corectitudinea algoritmului, trebuie mai intai sa demonstram urmatoarea lema:

Lema 1: Fiecare taietura faza reprezinta o taietura minima s-t, unde s si t sunt ultimele 2 noduri adaugate in faza curenta.

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 adaugat inainte de v se afla in multimi diferite. Fie w(C) costul taieturii C, Av multimea nodurilor adaugate inaintea lui v, Cv taietura lui Av ∪ v indusa de C, iar w(Cv) costul taieturii induse.

Vom arata prin inductie ca pentru fiecare nod activ v,

w(Av, v) ≤ w(Cv)

  1. Pentru primul nod activ, propozitia de mai sus este adevarata deoarece avem egalitate.
  2. Presupunem adevarata propozitia pentru toate nodurile active adaugate inaintea unui nod activ v, si fie u urmatorul nod activ ce urmeaza sa fie adaugat. Atunci avem:

w(Au, u) = w(Av, u) + w(Au\Av, u) = α

In continuare, avem w(Av, u) ≤ w(Av, v), deoarece atunci cand a fost ales, nodul v era mai puternic conectat decat u in raport cu Av. Prin inductie avem w(Av, v) ≤ w(Cv). Toate muchiile dintre Au\Av si u conecteaza multimi diferite ale taieturii C. Deci ele contribuie la w(Cu), dar nu si la w(Cv). Asadar:

α ≤ w(Cv) + w(Au\Av, u) ≤ w(Cu)

Concluzie: Cum t este tot timpul un nod activ in raport cu C, putem concluziona ca w(At, t) ≤ w(Ct), ceea ce demonstreaza ca orice taietura s-t are costul cel putin la fel de mare ca taietura faza.

Analiza complexitatii

In cadrul procedurii TaieturaMinima, vom apela procedura FazaTaieturiiMinime de O(|V|) ori. Observam ca in cadrul acestei din urma proceduri, avem nevoie de o structura de date care sa poata efectua in mod eficient urmatoarele operatii: extrage_cheia_maxima si creste_valoarea_unei_chei. Putem folosi un heap Fibonacci pentru a efecuta operatia extrage_cheia_maxima in O(log |V|) amortizat, iar pentru creste_valoarea_unei_chei in O(1) amortizat, obtinand astfel o complexitate finala de O(|V|*|E| + |V|2*log |V|). Nu recomand insa implementarea unei asemenea structuri in conditii de concurs, un heap binar fiind suficient, obtinandu-se astfel o complexitate de O(|V|*|E|*log |V|)

Probleme de taietura in concursurile de algoritmica

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