Lucrarea nr. 10

GRAFURI PONDERATE. APLICATII

1. DEFINITII

Se numeste graf ponderat ("weighted graph") un graf in cadrul căruia fiecărui arc ii este asociată o valoare. Valoarea asociata arcului are semnificaţia de "cost" a legaturii intre cele 2 noduri sau de "distanta" intre noduri.

2. ARBORI DE ACOPERIRE MINIMI

Fie G=(N,A) un graf conex in care fiecare arc (u,v) apartinand lui A are costul atasat c(u,v). Un arbore de acoperire al lui G este arborele liber care cuprinde toate nodurile din N si este un subgraf al lui G. Costul unui arbore de acoperire este suma costurilor tuturor arcelor cuprinse in arbore.

Aplicatii tipice ale arborilor de acoperire minimi se regasesc in proiectarea retelelor de comunicatii.

Exista mai multe metode de determinare a unui arbore minim asociat unui graf orientat; Se remarca algoritmul lui Prim, tehnica cautarii bazata pe prioritate si algoritmul lui Kruskal.

2.1. Algoritmul lui Prim

Algoritmul se bazeaza pe o proprietate, denumita si proprietatea arborilor de acoperire minimi.

Proprietatea arborilor de acoperire minimi se enunta astfel: Fie G=(N,A) un graf conex si o funtie de cost definita pe arcele sale. Fie U o submultime a multimii de noduri N. Daca (u,v) este un arc cu costul cel mai scazut astfel incat uiU iar viN-U, atunci exista un arbore de acoperire minim care include arcul (u,v).

Algoritmul lui Prim incepe prin introducerea primului nod (arbitrar) in multimea U (U=multimea nodurilor adaugate deja la arborele de acoperire). In continuare, intr-o maniera ciclica, este construit pas cu pas arborele de acoperire minim. La fiecare pas se selecteaza arcul cu cost minim (u,v) care conecteaza multimea U cu multimea N-U (uiU , viN-U) si se adauga acest arc arborelui, iar nodul v multimii U. Se repeta acest procedeu pana cand U=N.

procedure PRIM(G:Graf; var T:MultimeArce);
{Date de intrare: graful ponderat G=(N,A)}
{Date de iesire: arborele de acoperire minim T al grafului G,
  T:Multime_de_arce }

begin
   * initializeaza multimea arcelor arborelui,  T, ca fiind multimea vida
   * initializeaza  multimea nodurilor arborelui,  U, adaugandu-i un nod
   oarecare din N, considerat primul_nod_din_graf

   while (* nu s-au adaugat multimii de noduri  U toate nodurile lui N) do
      begin
          * gaseste arc(u,v) arcul cu costul cel mai redus care conecteaza
              U cu N-U,  avand  capetele u IN U si v IN N-U;
          * adauga arcul arc(u,v) la arborele de acoperire T
          * adauga nodul v la multimea U a nodurilor  arborelui T
      end
end; {PRIM}

Complexitatea relativa la timpul de executie a algoritmului este O(N2), deoarece se fac N iteratii (in ciclul while (N<>U)) pentru adaugarea tuturor nodurilor v la U, iar determinarea arcului minim in cadrul fiecarei iteratii se face in O(N).

2.2. Determinarea arborelui de acoperire minim prin metoda cautarii "bazata pe prioritate"

Dupa cum s-a aratat la tehnicile de traversare a grafurilor, nodurile pot fi divizate in trei clase:

clasa arbore ( noduri vizitate) - cuprinde nodurile care au fost extrase din structura de date utilizata in traversare
clasa vecinatate - cuprinde nodurile adiacente celor din arbore (au fost luate in considerare dar nu au fost inca vizitate)
clasa neintalnite - cuprinde nodurile la care nu s-a ajuns inca

Pentru a parcurge in mod sistematic o componenta conexa a unui graf se introduce un nod oarecare al componentei in clasa "vecinatate" si restul in clasa neintalnite. In continuare, pana la vizitarea tuturor nodurilor, se aplica urmatorul procedeu: se muta un nod x din clasa vecinatate in clasa arbore si se trec in clasa vecinatate toate nodurile neintalnite adiacente lui x. Metodele de parcurgere se diferetiaza in functie de politica de selectie a nodului x din vecinatate care e trecut in arbore.

Determinarea arborelui de acoperire minim se poate asimila cu acea traversare a grafului in care se alege din clasa vecinatate nodul cu prioritatea maxima, adica cel la care conduce arcul cu ponderea minima.

Se va utiliza o structura de coada bazata pe prioritate pentru memorarea nodurilor din clasa vecinatate (prioritatea maxima=nodul la care duce arcul de cost minim), cu urmatorii operatori:

Initializ_Coada_P;
Extrage_Coada_P -> nod ; returneaza nodul cel mai prioritar pentru a fi adaugat la arbore (cel mai prioritar= cel la care duce arcul de cost minim)
Actualiz_Coada_P(nod, prioritate) -> Boolean; verifica daca nodul apare in coada cu o prioritate cel putin egala cu cea precizata ca parametru. Daca nodul nu apare, el este inserat, iar daca apare in coada cu o prioritate mai mica (= cost mai mare) se realizeaza schimbarea prioritatii sale. Functia returneaza o valoare logica, semnificand faptul ca s-a produs sau nu o modificare

Arborele de acoperire minim se poate pastra intr-un tablou Parinte, in reprezentarea indicator spre parinte.

Pentru marcarea nodurilor vizitate, se foloseste un tablou de marcaje. Pentru un nod k al arborelui, marc[k] reprezinta costul arcului care il leaga pe k de parintele sau, Parinte[k]. Nodurile din clasa "vecinatate" sunt marcate cu valori negative in marc, iar nodurile din clasa "neintalnite" cu o valoare negativa maxima, -nevazut.

procedure Caut_prioritar ( k: nod );
begin
 if  (ActualizCoadaP(k,nevazut)) then  Parinte[k] = 0;
 repeat
    k := ExtrageCoadaP;
    marc[k] := -marc[k]; {k a fost adaugat la arbore}
    if (marc[k] = nevazut)  then marc[k] := 0;
    for  * fiecare nod t adiacent lui k do
         if (* nodul t inca nu este in arbore (marc[t^.nume] < 0)) then
            if  ActualizCoadaP(t^.nume,t^.cost) then
                begin
                  marc[t^.nume] := -(t^.cost);
                  Parinte[t^.nume] := k
                end
 until CoadaP_Vida;
end; { Caut_prioritar }

procedure ArboreMinim;
{Date de intrare: graful ponderat G=(N,A)}
{Date de iesire: padurea arborilor de acoperire minimi, in
                  reprezentarea "indicator spre parinte"  }
begin
* Initializeaza coada cu prioritati
* marcheaza toate nodurile k ca nevazute (marc[k]=-nevazut)
for * fiecare nod k do
     if (* k este inca nevazut)  then  Caut_prioritar(k)
end; { ArboreMinim }

Exemplul 1: Se considera graful din figura 1.

Fig. 1.Graf ponderat

Constructia arborelui de acoperire minim rezultat in urma algoritmului de cautare bazata pe prioritati parcurge urmatorii pasi: Se considera nod de start nodul 1 si se marcheaza ca vizitat (este trecut in clasa arbore). Clasa vecinatate va contine nodurile 2 [la dist 2 de 1] si 5[ la dist 5 de 1]. Urmatorul pas va selecta nodul 2, aflat la distanta 2 de singurul nod al arborelui. Clasa vecinatate va fi formata din nodurile 3[dist 3] de 2, 4[dist 7 de 2], 5[dist 5 de 1]. Urmatorul nod selectat va fi 3, aflat la distanta minima 3 de nodul 2 din arbore iar clasa vecinatate va deveni 4[dist 7 de 2], 5[dist 4 de 3], 6[dist 8 de 3]. Urmatorul nod selectat va fi 5, aflat la distanta 4 de nodul 3. In clasa vecinatate vor fi nodurile 4[dist 7 de 2] si 6[dist 8 de 3]. Se va alege nodul 4, clasa vecinatate contine nodul 6[dist 6 de 4] , nod care va fi selectat in pasul urmator, rezultand nodul 7[dist 9 de 6] in clasa vecinatate, care va fi ultimul selectat.

Fig. 2. Constructia arborelui de acoperire minim

2.3.Algoritmul lui Kruskal

Fie graful G=(N,A), N multimea nodurilor si A multimea arcelor. Algoritmul lui Kruskal de determinare a arborelui de acoperire minim T este un algoritm de tip Greedy, care alege la fiecare pas arcul cu cost minim dintre arcele grafului ramase inca in in evidenta. Arcul este adaugat daca aceasta operatie nu duce la formarea unui ciclu.

Initial, se formeaza o multime de N componente conexe, alcatuite fiecare din cate un nod si toate arcele A ale lui G se afla in evidenta pentru a fi eventual selectate.

La fiecare pas, algoritmul scoate arcul de cost minim dintre arcele inca neselectate. Daca capetele sale fac parte din componente conexe diferite arcul este adaugat lui T, si cele doua componente conexe sunt reunite. Altfel, daca cele doua capete sunt in cadrul aceleiasi componente conexe, arcul este ignorat. Algoritmul continua pana la ramanerea unei singure componente conexe ( in ipoteza ca graful initial a fost un graf conex).

Se propune ca implementarea algoritmului sa foloseasca o coada bazata pe prioritati pentru pastrarea ordonata a arcelor, si un TDA multime de submultimi pe care sunt definiti operatorii UNIUNE si CAUTA pentru memorarea componentelor conexe.

procedure  KRUSKAL;
{Date de intrare: graful ponderat G=(N,A)}
{Date de iesire: arborele de acoperire minim T al grafului G,
T:Multime_de_arce}
begin
  * initializeaza  arborele de acoperire T, prin T=multimea vida
  * initializeaza multimea de componente conexe, astfel incat fiecare
     componenta este alcatuita dintr-un nod al lui G
  * sorteaza arcele lui G in ordinea crescatoare a costului, inserindu-le intr-o
     coada cu prioritati
  while ( * exista mai multe componente conexe) do
      begin
        * scoate arcul de cost minim din coada; fie acesta arc(x,y)
        if ( * x si y  apartin la  componente conexe diferite ) then
        * adauga arc(x,y) la T si uneste cele 2 componente
      end
 end; { KRUSKAL }

Timpul de executie al algoritmului lui Kruskal depinde de metoda de implementare a cozii si a multimii de submultimi. Daca coada bazata pe prioritati este implementata cu ajutorul ansamblelor, si daca exista a arce, sunt necesare O(a log(a)) unitati de timp pentru a insera arcele in coada. Timpul necesar operatiilor UNIUNE si CAUTa depinde de implementarea multimii de submultimi, se pot obtine performante de ordinul O(alog(a)).

Exemplul 2: Se considera graful ponderat din figura 1. Arborele de acoperire minim se poate determina folosind algoritmul lui Kruskal urmand secventa de pasi de mai jos:

Fig. 3. Alg. lui Kruskal

Se selecteaza arcul avand costul minim , arcul (1,2) de cost 2 si se adauga la arbore. Urmatorul arc care se selecteaza este arcul (2,3) de cost 3 si se adauga la arbore. Urmeaza arcul (3,5) de cost 4 care se adauga si acesta la arbore. Urmatorul arc in ordinea costurilor este arcul (1,5) de cost 5; acesta insa nu poate fi adaugat, deoarece capetele sale apartin aceleiasi componente conexe si s-ar forma un ciclu. Se adauga arcul (4,6) de cost 6, apoi arcul (2,4) de cost 7. Urmatorul arc in ordinea crescatoare a costurilor este (3,6) de cost 8,dar acesta nu poate fi adaugat, avand capetele in aceeasi componenta conexa. Urmeaza arcul (6,7) de cost 9. In acest moment, toate nodurile apartin aceleiasi componente conexe, deci constructia arborelui a fost incheiata. Arborele de acoperire minim rezultat este reprezentat in figura 3 Arcele care fac parte din arbore au fost reprezentate ingrosat si numerotate in ordinea selectionarii lor.

Se observa ca s-a obtinut acelasi arbore minim de acoperire ca si in cazul aplicarii algoritmului de cautare bazata pe prioritati; Acest fapt insa nu este o regula generala, valabila in cazul tuturor grafurilor. Un graf poate avea mai multi arbori de acoperire minimi. In cadrul acestui exemplu, se observa insa ca ordinea de adaugare a arcelor de arbore nu este identica, chiar pentru arbori rezultati identici: arcul (2,4) care a fost al 4-lea in cazul algoritmului de cautare bazata pe prioritati este in cazul algoritmului lui Kruskal al 5-lea selectat.

3.DRUMUL MINIM

Problema drumului minim se refera la a gasi acel drum intr-un graf ponderat care conecteaza nodurile x si y si care se bucura de proprietatea ca suma ponderilor arcelor care il compun este minima.

Daca graful nu este ponderat, problema se reduce la determinarea acelui drum care conecteaza nodurile x si y si care este alcatuit dintr-un numar minim de arce. Algoritmul de cautare prin cuprindere, prezentat in lucrarea anterioara, rezolva aceasta problema.

Drumul minim intre doua noduri ale unui graf ponderat se poate determina prin tehnica cautarii bazate pe prioritate.

3.1.Determinarea drumurilor minime corespunzatoare unui nod al unui graf prin tehnica cautarii bazate pe prioritate

Aceasta problema se reduce la determinarea arborelui de acoperire corespunzator drumului minim care are drept radacina nodul in cauza. Solutionarea acestei probleme este asemanatoare cu determinarea arborelui de acoperire minim.

In cazul arborelui de acoperire minim s-a selectat la fiecare pas nodul din clasa vecinatate cel mai aproape de arbore. In cazul arborelui corespunzator drumurilor minime cu originea in x se va selecta nodul din clasa vecinatate cel mai aproape de nodul x.

Exemplul 3: Reluand analiza grafului din figura 1, drumurile minime cu originea in nodul 1 rezulta ca in figura 4.

Fig.4. Drumurile minime cu origine unica

Se observa faptul ca arborele de acoperire corespunzator drumurilor minime cu originea in nodul 1 este diferit de arborele minim de acoperire (fig.2)