Grafuri - Parcurgerea DF a grafurilor neorientate

Grafuri

Parcurgerea DF a grafurilor neorientate

Fie G=(V,M) un graf neorientat. Ca de obicei, notam n=|V| si m=|M|

Parcurgere in adancime a grafurilor (DF = Depth First) generalizeaza parcurgerea in preordine a arborilor oarecare. Eventuala existenta a ciclurilor conduce la necesitatea de a marca varfurile vizitate. Ideea de bazǎ a algoritmului este urmǎtoarea: se pleacǎ dinr-un varf i₀ oarecare, apeland procedura DF pentru acel varf. Orice apel de tipul DF(i) prevede urmǎtoarele operatii:

marcarea varfului i ca fiind vizitat;

pentru toate varfurile j din lista L_i a vecinilor lui i se executǎ apelul DF(j) daca si numai dacǎ varful j nu a fost vizitat.

Simpla marcare a unui varf ca fiind sau nu vizitat poate fi inlocuitǎ cu atribuirea unui numǎr de ordine fiecǎrui varf; mai precis, in nrdf(i), initial egal cu 0, va fi memorat al catelea este vizitat varful i nrdf(i) poartǎ numele de numǎrul (de ordine) DF al lui i

Este evident cǎ plecand din varful i₀ se pot vizita numai varfurile din componenta conexǎ a lui i₀. De aceea, in cazul in care graful nu este conex, dupǎ parcurgerea componentei conexe a lui i₀ vom repeta apelul DF pentru unul dintre eventualele varfuri incǎ neatinse.

procedure DF(i)

ndfndf+1; nrdf(i)ndf; vizit(i);

for toti jL_i

if nrdf(j)=0 then DF(j)

Programul principal este:

citeste graful;

ndf0;

for i=1,n

nrdf(i)0

for i=1,n

if nrdf(i)=0 then DF(i)

scrie nrdf;

Observatie. Dacǎ dorim doar sǎ determinǎm dacǎ un graf este conex, vom inlocui al doilea ciclu for din programul principal prin:

DF(1)

if ndf=n then write('CONEX')

else write('NECONEX');

Observatie. Parcurgerea DF imparte muchiile grafului in:

muchii de avansare: sunt acele muchii (i,j) pentru care in cadrul apelului DF(i) are loc apelul DF(j). Aceste muchii formeazǎ un graf partial care este o pǎdure: fiecare varf este vizitat exact o datǎ, deci nu existǎ un ciclu format din muchii de avansare.

muchii de intoarcere: sunt acele muchii ale grafului care nu sunt muchii de avansare.

Determinarea multimilor A si I a muchiilor de avansare si intoarcere, precum si memorarea arborilor partiali din padurea DF se poate face astfel:

in programul principal se fac initializarile:

A ; I

for i=1,n

tata(i)

instructiunea if din procedura DF devine:

if nrdf(j)=0

then AA; tata(j) i; DF(j);

else if tata(j)i

then II;

Exemplu. Pentru graful urmator:

cu urmatoarele liste ale vecinilor varfurilor:

L₁ L₂=; L₃=;

L₄ L₅=; L₆=;

L₇ L₈= L₉=

padurea DF este formata din urmatorii arbori partiali corespunzatori componentelor conexe:

Timpul cerut de algoritmul de mai sus este O(max)=O(n+m), adica liniar, deoarece:

pentru fiecare varf i, apelul DF(i) are loc exact o datǎ;

executarea unui apel DF(i) necesitǎ un timp proportional cu grad(i)=|L_i|; in consecintǎ timpul total va fi proportional cu m=|M|

Propozitie. Dacǎ (i,j) este muchie de intoarcere, atunci i este descendent al lui j

Muchia (i,j) este detectatǎ ca fiind muchie de intoarcere in cadrul executǎrii apelului DF(i), deci nrdf(j)<nrdf(i). Deoarece existǎ muchie intre varfurile i si j, rezultǎ cǎ in timpul executǎrii lui DF(j) va fi vizitat si varful i, deci i este descendent al lui j

Propozitia de mai sus spune cǎ muchiile de intoarcere leagǎ totdeauna douǎ varfuri situate pe aceeasi ramurǎ a pǎdurii partiale DF. In particular, nu exista muchii de traversare (care sa lege doi descendenti ai aceluiasi varf dintr-un arbore DF).

Observatie. Un graf este ciclic (contine cel putin un ciclu) dacǎ si numai dacǎ in timpul parcurgerii sale in adancime este detectatǎ o muchie de intoarcere.

Aplicatie. Sǎ se determine dacǎ un graf este ciclic si in caz afirmativ sǎ se identifice un ciclu.

Vom memora pǎdurea formatǎ din muchiile de avansare cu ajutorul vectorului tata si in momentul in care este detectatǎ o muchie de intoarcere (i,j) vom lista drumul de la i la j format din muchii de avansare si apoi muchia (j,i)

Procedura DF va fi modificata astfel:

procedure DF(i)

ndfndf+1; nrdf(i)ndf; vizit(i);

for toti jL_i

if nrdf(j)=0

then tata(j)i; DF(j)

else if tata(j) i

then ki;

while kj

write(k,tata(k)); ktata(k);

write(j,i); stop

end.

Observatii:

daca notam prin nrdesc(i) numarul descendentilor lui i in subarborele de radacina i, aceasta valoare poate fi calculata plasand dupa ciclul for din procedura DF instructiunea nrdesc(i) ndf-nrdf(i)+1

un varf j este descendent al varfului i in subarborele DF de radacina i nrdf(i) nrdf(j)<nrdf(i)+nrdesc(i)

O aplicatie: Problema barfei

Se considera n persoane. Fiecare dintre ele emite o barfa care trebuie cunoscuta de toate celelalte persoane.

Prin mesaj intelegem o pereche de numere (i,j) cu i,jI si cu semnificatia ca persoana i transmite persoanei j barfa sa, dar si toate barfele care i-au parvenit pana la momentul acestui mesaj.

Se cere una dintre cele mai scurte succesiuni de mesaje prin care toate persoanele afla toate barfele.

Cu enuntul de mai sus, o solutie este imediata si consta in succesiunea de mesaje: (1,2),(2,3),,(n-1,n),(n,n-1),(n-1,n-2),,(2,1)

Sunt transmit deci n-2 mesaje. Dupa cum vom vedea mai jos, acesta este numarul minim de mesaje prin care toate persoanele afla toate barfele.

Problema se complica daca exista persoane care nu comunica intre ele (sunt certate) si deci nu-si vor putea transmite una alteia mesaje.

Aceasta situatie poate fi modelata printr-un graf in care varfurile corespund persoanelor, iar muchiile leaga persoane care nu sunt certate intre ele. Vom folosi matricea de adiacenta a de ordin n in care a_ij este daca persoanele i si j sunt certate intre ele (nu exista muchie intre i si j) si in caz contrar.

Primul pas va consta in detectarea unui arbore partial; pentru aceasta vom folosi parcurgerea DF. Fiecarei persoane i ii vom atasa variabila booleana v_i, care este true daca si numai daca varful corespunzator a fost atins in timpul parcurgerii; initial toate aceste valori sunt false. Vom pune a_ij=2 pentru toate muchiile de inaintare.

v_i false, i=1,n

nr

DF(1)

if nr<n

then write('Problema nu are solutie (graf neconex)')

else rezolva problema pe arborele partial construit

unde procedura DF are forma cunoscuta:

procedure DF(i)

v_i true

for j=1,n

if a_ij=1 & not v_j

then a_ij 2; DF(j)

end

Sa observam ca in acest mod am redus problema de la un graf la un arbore! Descriem in continuare modul in care rezolvam problema pe acest arbore partial, bineinteles in ipoteza ca problema are solutie (graful este conex).

Printr-o parcurgere in postordine, in care vizitarea unui varf consta in transmiterea de mesaje de la fiii sai la el, radacina (presupusa a fi persoana 1) va ajunge sa cunoasca toate barfele. Aceasta se realizeaza prin apelul postord(1), unde procedura postord are forma:

procedure postord(i)

for j=1,n

if a_ij=2

then postord(j); write(j,i)

end

In continuare, printr-o parcurgere in preordine a arborelui DF, mesajele vor circula de la radacina catre frunze. Vizitarea unui varf consta in transmiterea de mesaje fiilor sai. Pentru aceasta executam apelul preord(1), unde procedura preord are forma:

procedure preord(i)

for j=1,n

if a_ij=2

then write(i,j); preord(j);

end

Observam ca atat la parcurgerea in postordine, cat si la cea in preordine au fost listate n-1 perechi (mesaje), deoarece un arbore cu n varfuri are n-1 muchii. Rezulta ca solutia de mai sus consta intr-o succesiune de 2n-2 mesaje. Mai ramane de demonstrat ca acesta este numarul minim posibil de mesaje care rezolva problema.

Propozitie. Orice solutie pentru problema barfei contine cel putin 2n-2 mesaje.

Sa consideram o solutie oarecare pentru problema barfei.

Punem in evidenta primul mesaj prin care o persoana a ajuns sa cunoasca toate barfele; fie k aceasta persoana. Deoarece celelate persoane trebuie sa le fi emis, inseamna ca pana acum au fost transmise cel putin n-1 mesaje. Dar k este prima persoana care a aflat toate barfele, deci celelalte trebuie sa mai afle cel putin o barfa. Rezulta ca in continuare trebuie sa apara inca cel putin n-1 mesaje. In concluzie, solutia considerata este formata din cel putin 2n-2 mesaje.

Circuitele fundamentale ale unui graf

Fie G=(V,M) un graf neorientat conex.

Fie A =(V,M') un arbore partial al lui G. Muchiile din M'M vor fi numite corzi.

Pentru fiecare coardǎ existǎ un unic drum, format numai din muchii din M', ce uneste extremitǎtile corzii. Impreunǎ cu coarda, acest drum formeazǎ un ciclu numit ciclu fundamental.

Fie G₁=(X₁,M₁) si G₂=(X₂,M₂) douǎ grafuri. Suma lor circularǎ este graful:

G₁ G₂ = (X₁ X₂, M₁ M₂M₁ M₂)

Observatii

Operatia    este comutativǎ si asociativǎ;

Dacǎ M₁ si M₂ reprezintǎ cicluri, atunci M₁ M₂ este tot un ciclu sau o reuniune disjunctǎ (in privinta muchiilor) de cicluri:

Teoremǎ. Pentru un graf si un arbore partial A al sǎu date, ciclurile fundamentale formeazǎ o bazǎ, adicǎ sunt indeplinite conditiile:

orice ciclu se poate exprima ca sumǎ circularǎ de cicluri fundamentale;

nici un ciclu fundamental nu poate fi exprimat ca sumǎ circularǎ de cicluri fundamentale.

Exemplu. Consideram urmatorul graf si un arbore partial al sau:

Ciclul se poate scrie ca o suma circulara de cicluri fundamentale astfel:

Demonstratie.

Considerǎm un ciclu in G, ale cǎrui muchii sunt partitionate in C= unde e₁,,e_k sunt corzi, iar e_k+1,,e_j sunt muchii din A

Fie C(e₁),,C(e_k) ciclurile fundamentale din care fac parte e₁,.,e_k. Fie C'=C(e₁) C(e_k). Vom demonstra cǎ C=C' (sunt formate din aceleasi muchii).

Presupunem cǎ C C'. Atunci C C' . Sǎ observǎm cǎ atat C cat si C' contin corzile e₁,.,e_k

Conform unei observatii de mai sus, C' si apoi C C' sunt cicluri sau reuniuni disjuncte de cicluri. Cum atat C cat si C' contin corzile e₁,,e_k si in rest muchii din A, rezultǎ cǎ C C' contine numai muchii din A, deci nu poate contine un circuit. Contradictie.

Fie un ciclu fundamental care contine coarda e. Fiind singurul ciclu fundamental ce contine e, el nu se va putea scrie ca sumǎ circularǎ de alte cicluri fundamentale.

Consecintǎ. Baza formatǎ din circuitele fundamentale are ordinul m n+1

Observatie. O muchie din C(e₁) C(e_k) este stearsǎ apare de numǎr par de ori.

Determinarea multimii ciclurilor fundamentale

Printr-o parcurgere a arborelui A, putem stabili pentru el legǎtura tata. Atunci pentru orice coardǎ (i,j) procedǎm dupǎ cum urmeazǎ:

Determinǎm vectorii:

u = (u₁=i, u₂=tata(u₁), , u_nu=tata(u_nu-1)=rad)

v = (v₁=j, v₂=tata(v₁), , v_nv=tata(v_nv-1)=rad)

Parcurgem simultan vectorii u si v de la stanga la dreapta si determinǎm cel mai mic indice k cu u_k=v_k

Atunci ciclul cǎutat este:

u₁=i, u₂, , u_k=v_k, , v₁=j, i

Observǎm cǎ pentru fiecare coardǎ, timpul este O(n)

Parcurgerea DF a grafurilor orientate

Algoritmul este acelasi ca la grafuri neorientate.

Arcele de avansare formeazǎ o pǎdure constituitǎ din arbori in care toate arcele au orientarea 'de la rǎdǎcinǎ cǎtre frunze', numitǎ 'pǎdure DF'.

Exemplu. Pentru graful:

obtinem pǎdurea:

si vectorul    nrdf = (1,2,3,4,5,6,7,8,9,10,11)

Parcurgerea DF imparte arcele (i,j) in 3 categorii:

arce de avansare, caracterizate prin nrdf(i)<nrdf(j)

arce componente ale pǎdurii DF;

arce ce leagǎ un varf de un descendent al sǎu care nu este fiu al sǎu;

arce de intoarcere, ce leagǎ un varf de un predecesor al sǎu in pǎdurea DF; evident nrdf(i)>nrdf(j)

arce de traversare: leagǎ douǎ varfuri care nu sunt unul descendentul celuilalt.

Pentru exemplul considerat avem:

Propozitie. Pentru orice arc de traversare (i,j) avem nrdf(i)>nrdf(j)

Sǎ presupunem prin absurd cǎ nrdf(i)<nrdf(j). Atunci in momentul in care s-a ajuns prima datǎ la i, varful j nu a fost incǎ atins. Din modul in care lucreazǎ algoritmul, (i,j) va fi arc de avansare:

sau

Observatie. Spre deosebire de arcele de traversare, arcele de intoarcere determinǎ un circuit elementar (prin adǎugarea unui astfel de arc la pǎdurea DF ia nastere un circuit elementar). Putem stabili dacǎ un arc (i,j) cu nrdf(i)>nrdf(j) este de intoarcere sau de traversare astfel:

k i;

while k 0 & k j

k tata(k)

if k=0 then write('traversare')

else write('intoarcere')

Parcurgerea BF a grafurilor neorientate

Fie un graf G=(V,M) si fie i₀ un varf al sau. In unele situatii se pune probleme determinarii varfului j cel mai apropiat de i₀ cu o anumita proprietate. Parcurgerea DF nu mai este adecvata.

Parcurgerea pe latime BF (Breadth First) urmareste vizitarea varfurilor in ordinea crescatoare a distantelor lor fata de i₀. Este generalizata parcurgerea pe niveluri a arborilor, tinandu-se cont ca graful poate contine cicluri. Va fi deci folosita o coada C

La fel ca si la parcurgerea DF, varfurile vizitate vor fi marcate.

Pentru exemplul din primul paragraf al acestui capitol, parcurgerea BF produce varfurile in urmatoarea ordine:

Algoritmul care urmeaza parcurge pe latime componenta conexa a lui i₀

for i=1,n

vizitat(i) false

C (i₀}

while C

i C; viziteaza i vizitat(i) true

for toti j vecini ai lui i

if not vizitat(j)

then j T C

Programul Java corespunzator foloseste:

Clasa Vector

Un vector (obiect de tipul Vector) are lungime variabila si contine obiecte oarecare.

Vector() : construieste vectorul vid (de lungime 0);

void addElement(Object) : adauga obiect la sfarsitul vectorului;

boolean remove Element(Object) : elimina, cu deplasare la stanga, prima aparitie;

boolean isEmpty() : verifica daca vectorul este vid;

Object firstElement() : intoarce primil element al vectorului.

Clasa infasuratoare Integer

Integer(int): constructor ce construieste un obiect ce contine intregul respectiv;

int intValue(): intoarce intregul asociat obiectului.

class BF

import java.util.*;

class nivel

mat[i] = new int[ntemp];

for (int j=0; j<ntemp; j++) mat[i][j] = temp[j];

IO.writeln(' ** ** ');

}

void parc()

}

}

La fel ca pentru parcurgerea DF, algoritmul poate fi completat pentru parcurgerea intregului graf, pentru determinarea unei paduri in care fiecare arbore este un arbore partial al unei componente conexe etc.