Fie G=(V,E)
un graf neorientat conex:
- un nod al grafului se numește punct de articulație sau nod critic dacă subgraful obținut prin eliminarea lui nu este conex;
- o muchie se numește punte sau muchie critică dacă graful parțial obținut prin eliminarea ei nu este conex;
- un graf neorientat se numește biconex dacă nu conține puncte de articulație;
- se numește componentă biconexă un subgraf biconex maximal – prin adăugarea încă unui nod nu mai este biconex.
Exemplu:
Graful inițial | Puncte de articulație | Punți | Componente biconexe |
Câteva observații:
- pentru fiecare muchie critică, cel puțin o extremitate este punct de articulație;
- fiecare punct de articulație face parte din cel puțin două componente biconexe;
- nodurile care fac parte dintr-un ciclu aparțin aceleiași componente biconexe;
- fiecare muchie critică reprezintă ea însăși o componentă biconexă;
- o muchie este critică dacă nu face parte dintr-un ciclu;
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:
- muchii de parcurgere, folosite la înaintarea în arbore
- muchii de întoarcere; o muchie
(k,x)
este de întoarcere dacăx
este ascendent al luik
în arboreleA
– nodulx
a fost descoperit anterior noduluik
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:
- un nod
k
al grafului, diferit de rădăcina arborelui DFS, este punct de articulație dacă și numai dacă are un descendent directx
în arboreleA
cu proprietatea că de la niciun descendent al luix
sau de lax
nu există muchie de întoarcere la niciun ascendent al luik
; - rădăcina arborelui DFS este punct de articulație dacă și numai dacă are în acest arbore cel puțin doi descendenți direcți.
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ă nodulk
în arborele DFS;nivel[rădăcină] = 1
;nivel[k] = nivel[tata[k]] + 1
;
nma[k]
– nivelul minim la care se poate ajunge dink
, 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 :- nivelul nodului curent
- minimul dintre nivelurile nodurilor cu care este legat nodul curent printr-o muchie de întoarcere
- minimul dintre nivelurile minime accesibile ale fiilor nodului curent din cadrul arborelui DFS
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, deoarece3
este fiu al lui2
șinivel[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 deoarece7
este fiu al lui5
șinivel[5] <= nma[7]
6
nu este punct de articulație; pentru singurul fiu al lui6
,8
relația estenivel[6] > nma[8]
7
este punct de articulație deoarece6
este fiu al lui7
șinivel[7] <= nma[6]
8
nu este punct de articulație deoarece nu are fii
Fie (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:
- stabilim
nivel[k] = nivel[tata[k]] + 1
– această valoare va rămâne neschimbată până la final; - inițializăm
nma[k] = nivel[k]
- parcurgem nodurile adiacente cu
k
. Fiex
un asemenea nod:- dacă
x
a fost deja parcurs și nu este tatăl luik
, muchia(k,x)
este muchie de întoarcere. Dacă este cazul actualizămnma[k]
la valoareanivel[x]
(dacănivel[x]
este mai mic decât valoarea actuală a luinma[k]
); - dacă
x
nu a fost încă parcurs, continuăm parcurgerea dinx
– îl adăugăm pe stivă/apel recursiv. La eliminarea de pe stivă/ revenirea din autoapel, actualizăm valoareanma[k]
la valoareanma[x]
(dacănma[k]
este mai mare decâtnma[x]
, acesta din urmă este calculat deja)
- dacă
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:
- la eliminarea de pe stivă a nodului
x
(revenirea din autoapel) verificăm dacă acest și nodul părintek
verifică relațianivel[k] <= nma[x]
; în caz afirmativ, decidem că nodulk
este critic; - pentru a stabili dacă rădăcina este punct de articulație trebuie să-i numărăm descendenții direcți în arbore.
- Observație: un punct de articulație poate fi descoperit de mai multe ori – dacă există mai mulți fii ai săi care respectă relația de mai sus.
//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:
- la eliminare de pe stivă a nodului
x
/revenirea din autoapel vom determina muchiile de parcurgere(k,x)
pentru care nivelul luik
este mai mic decât nivelul minim accesibil al luix
: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:
- utilizăm o stivă suplimentară
S
, pe care adaugăm noduri la vizitarea lor conform parcurgerii și le eliminăm la determinarea unei componente biconexe;- ordinea nodurilor din stiva
S
este cea a parcurgerii în adâncime;
- ordinea nodurilor din stiva
- dacă pentru nodul curent
k
avem un descendent directx
pentru carenivel[k] <= nma[x]
, vom elimina de pe stivă nodurile până la nodulx
, inclusiv acesta;- nodurile eliminate, împreună cu nodul
k
reprezintă o componentă biconexă; - eliminarea se face până la
x
, nu până lak
, deoarece între acestea, pe stivă, pot fi noduri din altă componentă biconexă.
- nodurile eliminate, împreună cu nodul
- Observație: condiția
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ă