Fie G=(V,E)
un graf neorientat conex:
Exemplu:
Graful inițial | Puncte de articulație | Punți | Componente biconexe |
Câteva observații:
Pentru a determina punctele de articulație și punțile se poate folosi un algoritm naiv, bazat pe eliminarea succesivă a câte unui nod (muchie) și verificarea conexității. Complexitatea acestor algoritmi este O(n*C)
, respectiv O(m*C)
, unde O(C)
este complexitatea algoritmului de verificarea a conexității (O(n*n)
dacă reprezentăm graful prin matrice de adiacență, O(n+m)
dacă reprezentăm graful prin liste de adiacențe).
În cele ce urmează vom prezentat un algoritm bazat pe parcurgerea în adâncime a grafului. Complexitatea sa este aceeași cu a parcurgerii în adâncime.
Considerăm G=(V,E)
graful dat și A
arborele de parcurgere în adâncime. Reamintim că muchiile graful pot fi doar:
(k,x)
este de întoarcere dacă x
este ascendent al lui k
în arborele A
– nodul x
a fost descoperit anterior nodului k
Pentru graful de mai sus, arborele de parcurgere este următorul – muchiile de parcurgere sunt desenate cu linii continue, cele de întoarcere cu linii întrerupte.
Observăm următoarele:
k
al grafului, diferit de rădăcina arborelui DFS, este punct de articulație dacă și numai dacă are un descendent direct x
în arborele A
cu proprietatea că de la niciun descendent al lui x
sau de la x
nu există muchie de întoarcere la niciun ascendent al lui k
;Pentru a determina punctele de articulație, punțile și componentele biconexe vom determina pentru fiecare nod k
următoarele informații:
nivel[k]
– nivelul pe care se află nodul k
în arborele DFS;
nivel[rădăcină] = 1
;nivel[k] = nivel[tata[k]] + 1
;nma[k]
– nivelul minim la care se poate ajunge din k
, mergând numai pe muchii de arbore și folosind ca ultimă muchie o muchie de întoarcere. Îl vom numi nivelul minim accesibil și este egal cu minimul dintre următoarele 3 valori :
Pentru graful de mai sus aceste valori sunt următoarele:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
nivel[k] |
1 |
2 |
3 |
4 |
3 |
5 |
4 |
6 |
nma[k] |
1 |
1 |
3 |
1 |
1 |
4 |
4 |
4 |
Cu ajutorul acestor valori, un nod k
care nu este rădăcina arborelui este punct de articulație dacă și numai dacă are cel puțin un fiu x
pentru care nivelul minim accesibil este mai mare sau egal cu nivelul nodului (nivel[k] <= nma[x]
). Să analizăm nodurile:
1
nu este punct de articulație, deoarece este rădăcina arborelui și are un singur descendent direct2
este punct de articulație, deoarece 3
este fiu al lui 2
și nivel[2] <= nma[3]
3
nu este punct de articulație, deoarece nu are niciun fiu4
nu este punct de articulație, deoarece nu are niciun fiu5
este punct de articulație deoarece 7
este fiu al lui 5
și nivel[5] <= nma[7]
6
nu este punct de articulație; pentru singurul fiu al lui 6
, 8
relația este nivel[6] > nma[8]
7
este punct de articulație deoarece 6
este fiu al lui 7
și nivel[7] <= nma[6]
8
nu este punct de articulație deoarece nu are fiiFie (k,x)
o muchie de arbore, în care k
este tatăl lui x
. Această muchie este critică dacă și numai dacă (nivel[k] < nma[x]
). Muchiile de întoarcere nu sunt niciodată muchii critice, deoarece aparțin întotdeauna unor cicluri.
Cele două șiruri de valori se construiesc în timpul parcurgerii DFS. Fie k
nodul curent în parcurgerea DFS:
nivel[k] = nivel[tata[k]] + 1
– această valoare va rămâne neschimbată până la final;nma[k] = nivel[k]
k
. Fie x
un asemenea nod:
x
a fost deja parcurs și nu este tatăl lui k
, muchia (k,x)
este muchie de întoarcere. Dacă este cazul actualizăm nma[k]
la valoarea nivel[x]
(dacă nivel[x]
este mai mic decât valoarea actuală a lui nma[k]
);x
nu a fost încă parcurs, continuăm parcurgerea din x
– îl adăugăm pe stivă/apel recursiv. La eliminarea de pe stivă/ revenirea din autoapel, actualizăm valoarea nma[k]
la valoarea nma[x]
(dacă nma[k]
este mai mare decât nma[x]
, acesta din urmă este calculat deja)Următorul pseudocod descrie cum se calculează pentru fiecare nod al grafului nivelul și nivelul minim accesibil, folosind parcurgerea în adâncime:
subprogram DFS(k, tata) V[k] ← true nivel[k] ← nivel[tata] + 1 nma[k] ← nivel[k] pentru x - nod adiacent cu k dacă x ≠ tata dacă V[x] = true atunci dacă nma[k] > nivel[x] atunci nma[k] ← nivel[x] sf_dacă altfel DFS(x,k) dacă nma[k] > nma[x] atunci nma[k] ← nma[x] sf_dacă // determinare puncte de articulație // determinare punți // determinare componente biconexe sf_dacă sf_dacă sf_pentru sf_subprogram
Pentru a determina punctele de articulație:
x
(revenirea din autoapel) verificăm dacă acest și nodul părinte k
verifică relația nivel[k] <= nma[x]
; în caz afirmativ, decidem că nodul k
este critic;//determinare puncte de articulație dacă nivel[k] ≤ nma[x] și nod ≠ rădăcină atunci //nodul k este punct de articulație sf_dacă
Pentru a determina punțile:
x
/revenirea din autoapel vom determina muchiile de parcurgere (k,x)
pentru care nivelul lui k
este mai mic decât nivelul minim accesibil al lui x
: nivel[k] < nma[x]
.//determinare punți dacă nivel[k] < nma[x] atunci //muchia (k,x) este punte sf_dacă
Pentru a determina componentele biconexe:
S
, pe care adaugăm noduri la vizitarea lor conform parcurgerii și le eliminăm la determinarea unei componente biconexe;
S
este cea a parcurgerii în adâncime;k
avem un descendent direct x
pentru care nivel[k] <= nma[x]
, vom elimina de pe stivă nodurile până la nodul x
, inclusiv acesta;
k
reprezintă o componentă biconexă;x
, nu până la k
, deoarece între acestea, pe stivă, pot fi noduri din altă componentă biconexă.nivel[k] <= nma[x]
are loc întotdeauna pentru rădăcina arborelui DFS, chiar dacă acesta nu este punct de articulație. În acest caz se determină o componentă biconexă din care face rădăcina. Acest lucru se întâmplă și când graful dat este biconex: determinarea componentei biconexe se face la revenirea în rădăcină.... V[k] ← true Adaugă(S,k) .... //determinare componente biconexe dacă nivel[x] ≤ nma[k] atunci câttimp Vârf(S) ≠ x execută Vârf(S) se adugă la componenta curentă Elimină(S) sf_câttimp x se adaugă la componenta curentă Elimină(S) k se adaugă la componenta curentă sf_dacă