Biconexitate

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 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:

• un nod 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;
• 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ă 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 :
  • 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 direct
• 2 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 fiu
• 4 nu este punct de articulație, deoarece nu are niciun fiu
• 5 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 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. Fie x un asemenea nod:
  • dacă 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]);
  • dacă 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:

• la eliminarea de pe stivă a nodului 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;
• 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 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:

• 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;
• dacă pentru nodul curent 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;
  • nodurile eliminate, împreună cu nodul k reprezintă o componentă biconexă;
  • eliminarea se face până la x, nu până la k, deoarece între acestea, pe stivă, pot fi noduri din altă componentă biconexă.
• 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ă