Grafuri

Studiul structurilor de tip graf, al reprezentărilor și algoritmilor fundamentali pe grafuri.

Grafuri neorientate — definiții și proprietăți de bază

Un graf neorientat G = (V, U) este format dintr-o mulțime V de vârfuri (noduri) și o mulțime U de muchii — perechi neordonate de vârfuri distincte. Muchia [x, y] este totuna cu [y, x], iar x și y se numesc extremități și sunt vârfuri adiacente; muchia este incidentă cu fiecare dintre ele.

Gradul unui vârf, d(x), este numărul de muchii incidente cu el. Formula care apare aproape la fiecare sesiune: suma gradelor tuturor vârfurilor este dublul numărului de muchii — fiecare muchie contribuie cu 1 la gradul fiecărei extremități. Consecință directă: numărul vârfurilor de grad impar este întotdeauna par.

Vocabular care se punctează exact:

• vârf izolat — grad 0; vârf terminal — grad 1;
• lanț — succesiune de vârfuri legate prin muchii; lanț elementar — nu repetă vârfuri; lanț simplu — nu repetă muchii;
• ciclu — lanț simplu care începe și se termină în același vârf; ciclu elementar — nu repetă vârfuri în afară de primul și ultimul;
• graf parțial — se obține eliminând muchii (vârfurile rămân toate); subgraf — se obține eliminând vârfuri împreună cu muchiile incidente. Inversarea celor două definiții e o greșeală de punctaj clasică.

Graful complet Kn are toate muchiile posibile: n(n-1)/2. Un graf este bipartit dacă vârfurile se pot împărți în două mulțimi astfel încât orice muchie să lege un vârf din prima mulțime cu unul din a doua. Graful hamiltonian conține un ciclu elementar care trece prin toate vârfurile; graful eulerian conține un ciclu care folosește fiecare muchie exact o dată — condiția clasică: graful este conex și toate vârfurile au grad par.

Grafuri orientate — arce, grade, drumuri

Într-un graf orientat (digraf), legăturile sunt arce — perechi ordonate (x, y): arcul iese din x (extremitatea inițială) și intră în y (extremitatea finală). Arcul (x, y) NU este același lucru cu arcul (y, x) — exact aici pierd puncte candidații care tratează matricea de adiacență ca fiind simetrică.

Fiecare vârf are două grade:

• gradul exterior d+(x) — numărul arcelor care ies din x;
• gradul interior d-(x) — numărul arcelor care intră în x.

Suma tuturor gradelor exterioare = suma tuturor gradelor interioare = numărul de arce.

Corespondentul lanțului este drumul (succesiune de vârfuri legate prin arce parcurse în sensul lor), iar corespondentul ciclului este circuitul. Un digraf cu n vârfuri are cel mult n(n-1) arce (fără bucle).

La conexitate apar două noțiuni distincte — o pereche cerută des la teorie:

• graful orientat este conex dacă graful neorientat obținut prin ignorarea sensurilor este conex;
• graful este tare conex dacă între oricare două vârfuri x și y există drum și de la x la y, și de la y la x.

O componentă tare conexă este un subgraf tare conex maximal. Orice graf tare conex este conex, dar reciproca este falsă — un contraexemplu minimal: două vârfuri și un singur arc între ele.

Reprezentarea grafurilor în memorie

Matricea de adiacență a este o matrice n x n cu a[i][j] = 1 dacă există muchia/arcul de la i la j și 0 altfel. Proprietăți care se cer:

• la graful neorientat matricea este simetrică față de diagonala principală, iar diagonala conține 0 (fără bucle); suma elementelor de pe linia i = gradul lui i, iar suma tuturor elementelor din matrice este dublul numărului de muchii;
• la graful orientat matricea nu este în general simetrică; suma pe linia i dă gradul exterior d+(i), iar suma pe coloana i dă gradul interior d-(i). Inversarea liniei cu coloana este capcana standard.

Matricea de adiacență ocupă O(n²) memorie indiferent câte muchii există și răspunde în O(1) la întrebarea „există muchia (i, j)?”.

Listele de adiacență rețin, pentru fiecare vârf, lista vecinilor săi (succesorilor, la digrafuri). Ocupă O(n + m) memorie și sunt eficiente pentru grafuri rare (cu puține muchii); parcurgerea vecinilor unui vârf durează cât gradul lui, nu O(n).

Lista de muchii reține perechile (extremitate, extremitate) — utilă de exemplu la Kruskal, unde muchiile trebuie sortate după cost.

Pentru grafuri ponderate se folosește matricea costurilor: c[i][j] = costul muchiei/arcului, 0 pe diagonală și o valoare convențională „infinit” unde nu există legătură directă. Greșeala frecventă la probleme: a pune 0 în loc de infinit pentru perechile fără muchie, ceea ce transformă absența legăturii într-o legătură gratuită.

Parcurgerea grafurilor: BFS și DFS

Parcurgerea în lățime (BFS — Breadth First Search) vizitează mai întâi vârful de start, apoi toți vecinii lui, apoi vecinii nevizitați ai acestora, în valuri. Structura de date suport este coada (FIFO): se scoate un vârf din coadă, se adaugă la coadă toți vecinii lui nevizitați, marcându-i vizitați la introducere. Proprietatea de aur, cerută la probleme: în graf neponderat, BFS găsește drumul cu număr minim de muchii de la sursă la orice alt vârf.

Parcurgerea în adâncime (DFS — Depth First Search) merge pe o ramură cât de departe se poate, apoi revine și explorează alternativele. Se implementează natural recursiv sau iterativ cu o stivă (LIFO). Perechea de asociat obligatoriu la teorie: BFS — coadă, DFS — stivă; inversarea lor este una dintre cele mai frecvente erori de grilă.

Ambele parcurgeri au complexitatea O(n + m) cu liste de adiacență și O(n²) cu matrice de adiacență, și ambele vizitează exact componenta conexă a vârfului de start.

De aici algoritmul standard pentru numărarea componentelor conexe: se parcurg vârfurile în ordine și, pentru fiecare vârf încă nevizitat, se lansează o parcurgere (BFS sau DFS) și se incrementează contorul. Numărul de lansări = numărul componentelor conexe.

Alte aplicații de examen: verificarea conexității (o singură parcurgere atinge toate vârfurile?), verificarea existenței unui lanț între două vârfuri, determinarea vârfurilor accesibile dintr-un vârf dat într-un digraf.

Arbori parțiali de cost minim: Kruskal și Prim

Un arbore parțial al unui graf conex cu n vârfuri este un graf parțial care este arbore: conex, fără cicluri, cu exact n-1 muchii. Într-un graf ponderat, arborele parțial de cost minim (APM) este arborele parțial cu suma costurilor muchiilor minimă. Ambii algoritmi clasici sunt aplicații ale metodei Greedy.

Kruskal lucrează cu muchiile: le sortează crescător după cost și le parcurge în această ordine, adăugând fiecare muchie la soluție doar dacă nu formează ciclu cu muchiile deja alese (adică extremitățile ei sunt în componente diferite). Se oprește după ce a acceptat n-1 muchii. În timpul rulării, soluția parțială poate fi o pădure — bucăți deocamdată nelegate între ele.

Prim lucrează cu vârfurile: pornește dintr-un vârf oarecare și crește un singur arbore, adăugând la fiecare pas muchia de cost minim care leagă un vârf din arbore de un vârf din afara lui. Soluția parțială este mereu conexă — exact invers decât la Kruskal; această diferență de comportament este întrebare de grilă recurentă.

Observații care aduc puncte:

• dacă toate costurile sunt distincte, APM-ul este unic; la costuri egale pot exista mai mulți arbori de același cost minim;
• APM-ul are întotdeauna exact n-1 muchii, indiferent de algoritm;
• Kruskal este avantajos la grafuri rare (puține muchii de sortat), Prim la grafuri dense.

Capcană: la Kruskal NU se sare o muchie doar pentru că are cost mare — se sare doar dacă ar închide un ciclu.

Drumuri de cost minim: Dijkstra și Bellman-Ford

Problema: într-un graf ponderat, să se afle costul minim al drumului de la un vârf sursă la celelalte vârfuri. Atenție la distincție: drumul de cost minim nu coincide neapărat cu drumul cu cele mai puține muchii — un ocol cu multe muchii ieftine poate bate legătura directă scumpă.

Dijkstra menține pentru fiecare vârf o distanță estimată d[x] (inițial 0 pentru sursă, infinit pentru rest) și o mulțime de vârfuri finalizate. La fiecare pas selectează vârful nefinalizat cu distanța estimată minimă — alegere de tip Greedy — îl marchează finalizat și relaxează muchiile care ies din el: dacă d[x] + c[x][y] < d[y], atunci d[y] se actualizează. Odată finalizat, un vârf nu se mai atinge.

Limita esențială, cerută explicit la teorie: Dijkstra funcționează corect doar cu costuri nenegative. Un cost negativ poate face ca un vârf deja finalizat să primească ulterior un drum mai bun, iar algoritmul nu mai revine asupra lui.

Bellman-Ford rezolvă și cazul costurilor negative: relaxează toate arcele, repetat, de n-1 ori (un drum elementar are cel mult n-1 arce). Dacă la o a n-a trecere vreo distanță încă scade, graful conține un circuit de cost negativ accesibil din sursă — și atunci noțiunea de drum minim nu mai are sens, pentru că circuitul poate fi parcurs oricât pentru a scădea costul. Prețul generalității: complexitate O(n·m), mai mare decât la Dijkstra.

Pentru distanțele minime între toate perechile de vârfuri se folosește algoritmul Roy-Floyd (Floyd-Warshall), cu trei cicluri imbricate și complexitate O(n³), în care vârful intermediar k se iterează în ciclul exterior.

Test — 6 întrebări ca la examen