Clasele 11-12 lecția 10 - 19 nov 2014

Grafuri

Exemple din lumea reală

• prieteniile / cunoștințele
• orașe cu drumuri între ele
• conducte prin care curge apă
• ierarhia unei companii (exemplu de arbore)

Definiții și terminologie

• definiție: un graf este o pereche (V, E) unde V este o mulțime (nodurile), iar E este o relație binară pe V (muchiile).
• reprezentare grafică
• într-un graf neorientat, muchiile sunt perechi neordonate; spunem că muchiile sunt adiacente nodurilor
• într-un graf orientat, muchiile sunt perechi ordonate; spunem că muchiile „intră” sau „ies” din noduri
• nodul v îi este adiacent lui u dacă există o muchie (u, v) ∈ E
  • relația de adiacență este simetrică pentru grafuri neorientate
• un graf se numește simplu dacă are cel mult o muchie între două noduri și nu are muchii de la un nod la el însuși
  • un graf care nu este simplu se numește multigraf; majoritarea problemelor de informatică sunt pe grafuri simple
• gradul unui nod este numărul de muchii incidente
  • în grafuri orientate, gradul este suma gradelor la intrare și la ieșire
• un graf G' = (V', E') este subgraf al lui G = (V, E) dacă V' ⊆ V și E' ⊆ E
• muchiile pot avea și costuri. Costul este o funcție c : E → R

Conexitate

• o cale este un șir de noduri astfel încât oricare două noduri consecutive sunt unite printr-o muchie
  • dacă există o cale de la u la v, spunem că v este accesibil din u.
  • o cale simplă conține doar vârfuri distincte
• un ciclu este o cale de cel puțin o muchie în care primul nod este egal cu ultimul
• un graf neorientat este conex dacă orice pereche de noduri sunt conectate printr-o cale
• componentele conexe ale unui graf neorientat sunt o partiție a grafului astfel încât oricare două noduri sunt accesibile unul dintr-altul dacă și numai dacă sunt în aceeași submulțime
  • echivalent, componentele conexe sunt clase de echivalență în funcție de relația „este accesibil din”
• un graf orientat este tare conex dacă oricare două noduri sunt reciproc accesibile
• componentele tare conexe ale unui graf sunt clase de echivalență în funcție de relația „sunt reciproc accesibile”
• (o relație de echivalență este reflexivă, simetrică și tranzitivă; exemple: =, = mod n)
• într-un graf neorientat, un nod este nod critic sau nod de articulație dacă, prin eliminarea lui, numărul de componente conexe crește
• similar, o muchie se numește muchie critică sau punte dacă, prin eliminarea ei, numărul de componente conexe crește
• un graf fără noduri de articulație se numește biconex
• componentele biconexe sunt subgrafuri biconexe maximale

Reprezentări

În primul rând, câtă informație este într-un graf? De câte numere avem nevoie pentru a descrie în mod unic graful? De $O(m+n)$. Numărul de noduri și lista muchiilor sunt suficiente.

Matricea de adiacență are avantajul că poate răspunde la întrebări de tipul „este u vecin cu v” în O(1). Ea are însă mari dezavantaje:

• necesită $O(n^{2})$ spațiu, asimptotic mai prost decât $O(m)$
• iterarea prin toate muchiile se face în timp $O(n^{2})$
• iterarea prin toți vecinii unui nod v se face în timp $O(n)$, în general mai prost decât grad(v)

Listele de adiacență inversează avantajele și dezavantajele:

• pot răspunde la întrebări de tipul „este u vecin cu v” în O(grad(u))
• necesită $O(m+n)$ memorie, deci optim
• iterarea prin toți vecinii unui nod v se face în timp O(grad(v)), deci optim
• iterarea prin toate muchiile se face în timp $O(m+n)$

Dacă ni se specifică la intrare gradele fiecărui nod, putem prealoca vectori de adiacență. Altfel trebuie să lucrăm cu liste înlănțuite. Listele se creează într-un vector prealocat de 2m muchii, nu prin alocare dinamică!

Parcurgerea în lățime (BFS)

O parcurgere (sau traversare) a unui graf este o modalitate de a vizita toate nodurile grafului într-o manieră controlată, pentru a afla informații despre graf.

Parcurgerea în lățime este o generalizare a algoritmului lui Lee pe matrice, pe care îl cunoașteți. În engleză, se numește breadth-first search (BFS). Ea pornește dintr-un nod ales s (numit sursă) și explorează toate nodurile accesibile. Pe parcurs, ea calculează două informații importante pentru fiecare nod descoperit: distanța minimă (ca număr de muchii) față de s și o cale de la s la d care atinge această distanță

Introducem aici și conceptul de culoare a unui nod. Aceste culori nu sunt reprezentate explicit în algoritm. Nodurile se împart în:

• albe (noduri încă nedescoperite)
• gri (noduri descoperite, dar încă neexplorate)
• negre (noduri complet explorate)

Parcurgerea BFS menține o coadă cu nodurile gri. La fiecare pas, primul nod din coadă este explorat; explorarea înseamnă că obținem accesul la succesorii săi, pe care îi adăugăm în coadă. Apoi nodul este înnegrit și eliminat din coadă. Algoritmul asociază și calculează trei valori fiecărui nod u:

• c[u]: culoarea nodului u
• d[u]: distanța minimă de la s la u
• p[u]: nodul predecesor al lui u pe una din căile de la s la u care ating distanța minimă

BFS(G<V, E>, s) {
  // inițializare
  for (u ∈ V) {
    c[u] = alb
    d[u] = ∞
    p[u] = nedefinit
  }
  c[s] = gri
  d[s] = 0
  Q = coadă cu un singur element, s

  // buclă
  while (Q este nevidă) {
    u = dequeue(Q)
    for ((u, v) ∈ E) {
      if (c[v] == alb) {
        // am descoperit un nod nou, o primă cale (minimă) către v
        c[v] = gri;
        d[v] = d[u] + 1
        p[v] = u
        enqueue(v)
      }
    }
    c[u] = negru
  }
}

Timpul de rulare este $O(m+n)$. Inițializarea este $O(n)$, apoi fiecare nod și fiecare muchie sunt parcurse o singură dată. Remarcăm, în special, că valorile p și d sunt atribuite o singură dată pentru fiecare nod.

Demonstrația de corectitudine a distanțelor calculate

Este intuitiv, dar nu chiar banal, că parcurgerea BFS vizitează nodurile în ordinea distanței față de s (de aici îi derivă și numele). Iată o demonstrație care scoate în evidență unele proprietăți interesante ale vectorului d.

Fie δ(s, u) distanța minimă teoretică (cel mai scurt drum între s și u). Dorim să demonstrăm că δ(s, u) = d[u] pentru fiecare nod u.

• Algoritmul funcționează evident și pentru nodurile inaccesibile din s. Acestea au δ(s, u) = ∞. Algoritmul BFS setează această valoare în cursul inițializării, apoi nu vizitează niciodată acele noduri, deci nu modifică d[u].
• Propoziție: Pentru orice muchie (u, v), δ(s, v) ≤ δ(s, u) + 1 -- evident
• Propoziție: Coada conține, la orice moment, noduri cu d crescător, ale căror valori d diferă prin cel mult 1.
  • demonstrație: prin inducție după operațiile pe coadă
• Demonstrăm că d[v] ≥ δ(s, v)
  • Demonstrația este inductivă după numărul de modificări în d
  • cazul de bază: la început, d[s] = 0 și d[v] = ∞ pentru celelalte noduri
  • la modificarea lui d[v] avem d[v] = d[u] + 1 ≥ δ(s, u) + 1 ≥ δ(s, v)
• Demonstrăm că d[v] = δ(s, v)
  • demonstrație: presupunem că există noduri care nu respectă această proprietate. Fie v unul dintre ele, cu δ(s, v) minim.
  • cum d[v] ≥ δ(s, v), rezultă că d[v] > δ(s, v)
  • fie u nodul anterior pe una din cele mai scurte căi de la s la v, așadar δ(s, v) = δ(s, u) + 1
  • prin alegerea lui v, rezultă că d[u] = δ(s, u) și deci d[v] > d[u] + 1
  • cum s-ar putea întâmpla așa ceva?
  • ce culoare poate avea v în momentul în care algoritmul îl scoate pe u din coadă? Pe toate cele trei cazuri ajungem la contradicții.

Parcurgerea în adâncime (DFS)

Parcurgerea în adâncime, după cum subliniază și numele ei, preferă să parcurgă nodul în adâncime, explorând complet un nod înainte de a trece la frații lui.

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] = ∞;
    p[u] = NIL;
    culoare[u] = alb;
  }
  timp = 0;
  for (u nod în G) {
    if (culoare[u] == alb) {
      DFS(u);
    }
  }  
}

Observații despre acest cod:

• Este recursiv. :-)
• Funcționează pe grafuri orientate sau neorientate.
• El calculează o mulțime de informații care sunt utile din punct de vedere teoretic, dar de obicei nu apar în implementare.
• Timpul este o variabilă globală care crește la fiecare „eveniment”.
• d[u] și f[u] rețin timpul de descoperire, respectiv de terminare a explorării unui nod.
• p[u] reține părintele fiecărui nod, respectiv nodul prin care s-a ajuns la acel nod.
• Nodurile sunt inițial albe, devin gri în timpul explorării, apoi negre când sunt explorate complet.
• În fapt, nodurile gri reprezintă nodurile de pe stiva recursivității.
• Algoritmul nu are legătură cu distanțele. Noduri foarte apropiate de sursă pot fi vizitate ultimele.
• Dacă graful nu este conex, DFS() va înnegri doar o parte din graf. Dacă dorim să-l explorăm complet, avem nevoie de funcția DFS-master().

Complexitate

DFS-master() este evident O(n). DFS() execută bucla for de m ori în total (căci inspectează fiecare muchie exact o dată pentru grafuri orientate, respectiv de două ori pentru grafuri neorientate). Așadar, complexitatea este $O(m+n)$, ca și pentru BFS.

Comparație între BFS și DFS

• DFS se implementează ceva mai ușor decât BFS.
• BFS este adesea o problemă în sine, pe când DFS este doar o metodă sistematică de a explora graful, servind ca suport pentru alte probleme.
• BFS calculează distanțele minime de la sursă, pe când DFS nu poate garanta decât accesibilitatea, nu și distanțele.
• Atât BFS cât și DFS pot avea nevoie de memorie suplimentară O(n).
  • Dați exemple de grafuri pe care BFS, respectiv DFS necesită memorie O(n).
• Conceptual, atât BFS cât și DFS folosesc trei culori pentru noduri (alb, gri și negru).

Proprietăți ale DFS

Vectorul p stochează, în fapt, un arbore, căci muchiile (p[u], u) nu închid cicluri. Acest arbore se numește arborele parcurgerii sau arbore DFS și coincide cu arborele de apeluri recursive.

În urma parcurgerii în adâncime a unui graf orientat, muchiile grafului se împart în patru categorii importante:

• 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.

În grafurile orientate, parcurgerea DFS generează doar muchii de arbore și înapoi, niciodată înainte sau transversale.

Timpii de vizitare d și f dau indicii despre raporturile dintre noduri în arborele DFS. Două noduri u și v vor fi mereu în unul din aceste cazuri:

1. intervalele (d[u], f[u]) și (d[v], f[v]) sunt disjuncte; u și v fac parte din subarbori DFS diferiți
2. d[u] < d[v] < f[v] < f[u] și v este urmaș al lui u în arborele DFS
3. d[v] < d[u] < f[u] < f[v] și u este urmaș al lui v în arborele DFS

Cazuri ca d[u] < d[v] < f[u] < f[v] sunt imposibile. Demonstrație: presupunem că d[u] < d[v] și vedem unde poate fi f[u].

Aplicație: sortare topologică

Definiție; se aplică grafurilor orientate aciclice (dag).

Exemple:

• lista de sarcini sau de buguri într-un proiect;
• lista de dependențe între cursuri la o universitate;
• lista de moșteniri la clasele din C++/Java (compilatorul trebuie să știe);
• cum se îmbracă un om.

Cerință echivalentă: să se scrie nodurile grafului, de la stânga la dreapta, într-o astfel de ordine încât toate muchiile grafului să meargă de la stânga la dreapta.

Sortarea topologică este o relație de ordine parțială, spre deosebire de relația "<" pe numere, care este o relație de ordine totală.

Un algoritm simplu folosește o coadă de noduri de grad la intrare 0. Algoritmul are complexitate O(V + E). El este, în fapt, o parcurgere BFS cu sursă multiplă.

Al doilea algoritm este o aplicație directă a DFS: nodurile sunt afișate în ordine descrescătoare a lui f. Echivalent, la terminarea vizitării unui nod, îl adăugăm la începutul listei-soluție (din nou, vectorul f nu este explicit necesar).

În ambele cazuri, când știm că graful nu admite o sortare topologică? Hint: un graf orientat este aciclic ⇔ în DFS nu există back edges.

Demonstrație că DFS sortează topologic:

• trebuie să arătăm că, pentru orice muchie (u,v), f[v] < f[u]
• când muchia (u,v) este explorată, v nu poate fi gri, căci (u,v) ar fi back edge
  • dacă v este alb, el devine urmaș al lui u și va fi înnegrit înainte de a reveni la u
  • dacă v este negru, f[v] era deja setat, pe când f[u] va fi setat la un moment viitor

Temă

• Tema 7 seniori