Note de curs, clasele 9-10, 28 noiembrie 2013

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 („linii”); spunem că muchiile sunt adiacente nodurilor
• într-un graf orientat, muchiile sunt perechi ordonate („săgeți”); spunem că muchiile „intră” sau „ies” din noduri
• nodul v îi este adiacent lui u dacă există o muchie (u, v) ∈ E
  • relația este simetrică dacă graful este neorientat
• 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
• dacă V' ⊆ V, subgraful indus de V' este graful cu nodurile V' și muchiile din E care leagă noduri din V'
• muchiile pot avea și costuri. Costul este o funcție c : E → R

Exemple din lumea reală

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

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

Grafuri speciale

• un graf complet este un graf neorientat în care între orice două noduri există o muchie
• un graf bipartit este un graf neorientat în care nodurile pot fi partiționate în două submulțimi V₁ și V₂ astfel încât toate muchiile să ducă din V₁ în V₂
• un arbore este un graf neorientat aciclic
  • o pădure este un graf aciclic (fiecare din componentele sale conexe este un arbore)
• un dag (directed acyclic graph) este un graf orientat aciclic (folosim această prescurtare întrucât conceptul apare des)

Proprietăți

• suma gradelor este 2 |E|
  • corolar: numărul nodurilor de grad impar este par
• un arbore este un graf aciclic maximal
• un arbore este un graf aciclic cu |V| - 1 muchii
• un arbore este un graf conex minimal
• un arbore este un graf conex cu |V| - 1 muchii

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). Numărul de noduri și lista muchiilor sunt suficiente.

Matricea de adiacență are marele avantaj 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²) spațiu, asimptotic mai prost decât O(m)
• iterarea prin toți vecinii unui nod v se face în timp O(n), în general mai prost decât grad(v)
• iterarea prin toate muchiile se face în timp O(n²)

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 a unui graf

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 și explorează toate nodurile accesibile. Pe parcurs, ea calculează o informație importantă pentru fiecare nod descoperit: distanța minimă față de s.

• folosește o coadă de noduri descoperite, dar încă neexplorate
• folosește, conceptual, trei culori pentru fiecare nod: alb (nod nedescoperit), gri (nod descoperit, dar neexplorat), negru (nod explorat complet)
  • aceste culori nu sunt reprezentate explicit în algoritm
• exemplu grafic
• vedem că algoritmul expandează o frontieră de noduri tot mai depărtate de s; de aceea se numește parcurgere în lățime
• algoritmul calculează distanța fiecărui nod până la s și drumul pe care se obține această distanță

Cod aici.

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

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.

• trebuie să ținem cont și de nodurile inaccesibile din s, pentru care δ(s, u) = ∞
• pentru orice muchie (u, v), δ(s, v) ≤ δ(s, u) + 1 -- evident
• d[v] ≥ δ(s, v)
  • demonstrație: inductiv, pentru tot graful, 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)
• coada conține mereu noduri cu d crescător și cu diferență de cel mult 1
  • demonstrație: prin inducție după operațiile pe coadă
• 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.

Probleme

• pentru avansați: problemele de la Șumen 2013 (căutați 2013-11-24, seturile de probleme A și B)
• implementare BFS: Capitala, Graf, Barbar
• orice arbore este bipartit
• într-un graf neorientat cu >= 2 noduri există două noduri cu același grad
• într-un graf cu 6 noduri există un subgraf complet cu trei noduri sau un subgraf cu 3 noduri fără muchii
• problema celebrității O(n)
• Un ciclu eulerian este un ciclu care vizitează fiecare muchie a grafului exact o dată. Care este condiția necesară și suficientă ca un graf să admită un ciclu eulerian?