Note de curs, clasele 11-12, 27 martie 2014

From Algopedia
Revision as of 01:29, 26 March 2014 by Cata (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Componente biconexe, puncte de articulație, punți

Recapitulare

Într-o lecție trecută am discutat despre parcurgerea în adâncime, sortarea topologică și componentele tare conexe. Reamintim câteva dintre aceste noțiuni, căci se aplică și la lecția de astăzi.

Parcurgerea în adâncime (DFS) este o rutină recursivă simplă:

DFS(nod u) {
  vizitat[u] = true;
  for (v in vecini(u)) {
    if (!vizitat[v]) {
      DFS(v);
    }
  }
}

DFS-master(graf G) {
  for (u nod în G) {
    vizitat[u] = false;
  }
  for (u nod în G) {
    if (!vizitat[u]) {
      DFS(u);
    }
  }  
}

Conceptual (și uneori și în practică), extindem această rutină cu trei informații noi:

  • culoarea unui nod, care este alb cât timp nodul nu a fost descoperit, gri cât timp nodul este în curs de explorare și negru la sfârșitul vizitării nodului;
  • părintele unui nod, care este nodul prin care am ajuns prima oară la nodul respectiv;
  • timpii de descoperire și de finalizare a unui nod.
int timp;

DFS(nod u) {
  culoare[u] = gri;
  d[u] = ++timp;
  foreach (v vecin al lui u) {
    if (culoare[v] == alb) {
      p[v] = u;
      DFS(v);
    }
  }
  culoare[u] = negru;
  f[u] = ++timp;
}

DFS-master(graf G) {
  for (u nod în G) {
    d[u] = f[u] = 0;
    p[u] = NIL;
    culoare[u] = alb;
  }
  timp = 0;
  for (u nod în G) {
    if (culoare[u] == alb) {
      DFS(u);
    }
  }  
}

Într-un graf orientat, o parcurgere DFS clasifică muchiile în patru categorii:

  • muchiile de arbore (tree) sunt acele muchii pe care DFS() se reapelează recursiv. Ele sunt stocate în vectorul p. Ele duc de la un nod gri la unul alb.
  • muchiile înapoi (back) sunt muchii care ar închide un ciclu între nodurile de pe stivă. Ele duc de la un nod gri la alt nod gri.
  • muchiile înainte (forward) sunt muchii care duc de la un nod gri la un nod negru din subarborele lui DFS.
  • muchiile transversale (cross) sunt muchii care duc de la un nod gri la un nod negru dintr-un subarbore DFS parcurs anterior.

Într-un graf neorientat, nu există decât muchii tree sau back (de ce?).

Definiții

Fie un graf neorientat G = (V, E).

  • Un punct de articulație este un nod a cărui eliminare numărul de componente conexe ale lui G crește.
  • O punte este o muchie prin a cărei eliminare numărul de componente conexe ale lui G crește.

Dacă G este presupus conex, putem reformula definițiile ca:

  • Un punct de articulație este un nod a cărui eliminare G devine neconex.
  • O punte este o muchie prin a cărei eliminare G devine neconex.

Pentru clarificare, un nod este eliminat împreună cu toate muchiile incidente. La eliminarea unei muchii, nodurile de la cele două capete nu sunt eliminate.

Graful G este biconex dacă prin eliminarea oricărui nod G rămâne conex.

Pentru componentele biconexe există două definiții asemănătoare, dar nu identice. Când primiți o problemă de biconexitate, citiți cu atenție enunțul pentru a vedea în ce caz vă aflați.

  • (Cormen) O componentă biconexă este un subset maximal de muchii astfel încât oricare două se află pe un ciclu comun.
  • (Wikipedia) O componentă biconexă este un subgraf biconex maximal.

Exemplu

În acest graf am evidențiat punctele de articulație (4, 9, 10, 11, și 14) și punțile ((4, 9), (10, 13), (11, 14), (14, 15)).

Componentele biconexe diferă în funcție de ce definiție alegem:

  • Cormen: muchiile subgrafurilor {1, 2, 3, 4, 5}, {4, 6, 7, 8}, {9, 10, 11, 12}
  • Wikipedia: subgrafurile {1, 2, 3, 4, 5}, {4, 6, 7, 8}, {9, 10, 11, 12}, {10, 13}, {11, 14}, {14, 15}.

Pe baza acestei imagini putem sublinia diferențele dintre cele două definiții:

  • Definiția din Wikipedia are avantajul că orice nod aparține cel puțin unei componente biconexe. Definiția din Cormen permite existența unor noduri care să nu facă parte din nicio componentă conexă.
  • Definiția din Wikipedia are dezavantajul că generează componente suprapuse (noduri care fac parte din mai multe componente).
  • În esență, definiția din Cormen este o partiție a muchiilor care nu sunt punți.
  • Definiția din Cormen exclude subgrafurile cu două noduri.

Proprietăți

Sunt adevărate sau false următoarele propoziții? Schițați o demonstrație sau dați contraexemple.

  • O frunză (nod de grad 1) nu este niciodată punct de articulație. OK, asta e banală. :-)
  • Dacă u este punct de articulație, atunci cel puțin una dintre muchiile incidente lui u este punte.
  • Dacă (u, v) este o punte, atunci u și v sunt puncte de articulație.
    • Cazul în care u sau v sunt frunze este evident. Dar în afara acestui caz particular?
  • Dacă u și v sunt puncte de articulație și există o muchie (u, v) ∈ E, atunci (u, v) este punte.
  • u este punct de articulație dacă și numai dacă există două noduri v și w (diferite între ele și diferite de u) astfel încât toate căile de la v la w trec prin u
  • (u, v) este punte dacă și numai dacă există două noduri x și y (diferite între ele, dar posibil egale cu u sau v) astfel încât toate căile de la x la y trec prin muchia (u, v).

Găsirea punctelor de articulație și a punților

Toate aceste proprietăți ale grafului pot fi aflate printr-o singură parcurgere DFS dintr-un nod oarecare. Pe parcursul parcurgerii, calculăm următoarele valori pentru fiecare nod u:

  • este adâncimea în arborele DFS a nodului u (distanța până la rădăcină);
  • este adâncimea minimă a oricărui vecin a oricărui descendent v al lui u (inclusiv u însuși).

Putem defini recurent ca

În cuvinte, încercăm să determinăm dacă u are acces la porțiunea din graf de deasupra părintelui său pe un drum care să nu treacă prin părinte.

Cu aceste notații,

  • Rădăcina parcurgerii DFS este punct de articulație dacă are doi sau mai mulți fii.
  • Un nod u diferit de rădăcină este punct de articulație dacă are cel puțin un fiu v pentru care low[v] ≥ d[u].
  • O muchie (u, v) este punte dacă u este părintele DFS al lui v' și low[v] ≥ d[u].

Pentru a demonstra prima afirmație, să ne amintim că în parcurgerea DFS a unui graf neorientat nu există muchii cross. Așadar, dacă rădăcina are doi fii, ei nu sunt conectați decât prin intermediul rădăcinii, deci eliminarea rădăcinii ar deconecta graful.

Celelalte două afirmații sunt constructive: nodul v nu este conectat de rădăcină decât prin nodul u, deci eliminarea nodului u (sau a muchiei (u, v)) ar deconecta graful.

Pseudocod

// returnează nivelul maxim la care pot urca u sau oricare din descendenții lui
int dfs(int u, int tata) {
  d[u] = d[tata] + 1;
  low = d[u];
  for (v in vecini(u)) {
    if (v != tata) {
      if (d[v] > 0) {               // (u, v) este muchie înapoi
        if (d[v] < min) {
          low = d[v];
        }
      } else {                      // (u, v) este muchie de arbore
        int lowV = dfs(v, u);
        if (lowV >= d[u]) {
          printf("%d este punct de articulație, u");
          if (lowV == d[v]) {
            printf("În plus, (%d, %d) este punte", u, u, v);
          }
        } else if (lowV < low) {
          low = lowV;
        }
      }
    }
  }
  return low;
}

Găsirea componentelor biconexe

Vom exemplifica găsirea componentelor biconexe conform definiției din Cormen. Intuitiv, vrem ca imediat ce descoperim un nod v care este rădăcina unei componente biconexe, să tipărim acea componentă, apoi să o eliminăm din arborele DFS. Este suficient să ștergem muchia (u, v), deoarece știm că astfel tot subarborele lui v va deveni inaccesibil din u.

Dar implementarea aceasta este problematică, deoarece noi nu construim propriu-zis un arbore DFS. Tot ce vedem la fiecare moment este „felia verticală” corespunzătoare stivei de apeluri DFS de la acel moment. În practică, folosim o stivă pe care punem muchiile pe măsură ce le descoperim. Când determinăm că v este punct de articulație, scoatem de pe stivă muchiile recent adăugate până când găsim muchia (u, v). Toate aceste muchii formează o componentă biconexă. Muchia (u, v) însăși face parte din componenta biconexă numai dacă nu este punte.

Exemplu: pentru graful de mai sus, pornim parcurgerea din nodul 1.

nodul curent muchia curentă stiva DFS stiva de muchii observații
1 (1, 2) 1 (1, 2)
2 (2, 3) 1, 2 (1, 2), (2, 3)
3 (3, 4) 1, 2, 3 (1, 2), (2, 3), (3, 4)
4 (4, 5) 1, 2, 3, 4 (1, 2), (2, 3), (3, 4), (4, 5)
5 (5, 1) 1, 2, 3, 4, 5 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1)
4 (4, 6) 1, 2, 3, 4 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6) 5 este explorat complet, revenim la 4
6 (6, 7) 1, 2, 3, 4, 6 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6), (6, 7)
7 (7, 8) 1, 2, 3, 4, 6, 7 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6), (6, 7), (7, 8)
8 (8, 4) 1, 2, 3, 4, 6, 7, 8 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6), (6, 7), (7, 8), (8, 4)
7 (7, 4) 1, 2, 3, 4, 6, 7 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6), (6, 7), (7, 8), (8, 4), (7, 4) 8 este explorat complet, revenim la 7
6 -- 1, 2, 3, 4, 6 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6), (6, 7), (7, 8), (8, 4), (7, 4) 7 este explorat complet, revenim la 6
4 -- 1, 2, 3, 4 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (4, 6), (6, 7), (7, 8), (8, 4), (7, 4) 6 este explorat complet, revenim la 4

În acest moment, algoritmul decide că 4 este punct de articulație și tipărește toate muchiile din stivă începând cu (4, 6). Muchia (4, 6) face și ea parte din componenta biconexă, deoarece nu este punte.

Muchiile (1, 2), (2, 3), (3, 4), (4, 5) și (5, 1) rămân pe stivă și vor fi puse într-o componentă biconexă viitoare. Parcurgerea continuă cu muchia (4, 9).

Probleme