Descrierea grafurilor

Iată o modalitate de reprezentare a unei rețele sociale:

Dacă există o linie între numele a două persoane înseamnă că se cunosc reciproc. Dacă nu există nici o linie între două nume, atunci cei doi nu se cunosc. Relaţia "se cunosc reciproc" merge în ambele sensuri; de exemplu, deoarece Audrey îl cunoaşte pe Gayle, asta înseamnă că și Gayle o cunoaşte pe Audrey.

Această rețea socială este un graf. Numele persoanelor reprezintă nodurile grafului. (Dacă vorbim despre unul singur, îl numim nod.) Fiecare linie este o muchie; ea conectează două noduri. Notăm muchia care conectează nodurile $u$u și $v$v cu perechea $(u, v)$left parenthesis, u, comma, v, right parenthesis. Deoarece relația "se cunosc reciproc" are loc în ambele sensuri, acest graf este neorientat. O muchie neorientată $(u, v)$left parenthesis, u, comma, v, right parenthesis coincide cu $(v, u)$left parenthesis, v, comma, u, right parenthesis. Mai târziu, vei vedea grafuri orientate, în care relațiile dintre noduri nu au loc neapărat în ambele sensuri. Într-un graf neorientat, o muchie între două noduri, cum ar fi muchia dintre Audrey și Gayle, este incidentă celor două noduri. Spunem despre două noduri conectate de o muchie că sunt adiacente sau vecine. Numărul de muchii incidente la unui nod reprezintă gradul nodului.

Audrey şi Frank nu se cunosc. Să presupunem că Frank dorea să fie prezentat lui Audrey. Cum ar putea să fie prezentat? Ei bine, o știe pe Emily, ea îl știe pe Bill, iar acesta o știe pe Audrey. Spunem că există un drum de trei muchii între Frank şi Audrey. De fapt, acesta este cel mai direct mod prin care Frank o poate întâlni pe Audrey; nu există niciun alt drum între ei cu mai puţin de trei muchii. Drumul între două noduri care are cel mai mic număr de muchii se numește drumul cel mai scurt. În figura de mai jos, este îngroșat drumul cel mai scurt:

Un drum care pornește dintr-un anumit vârf și se termină în același nod se numește ciclu. Rețeaua socială conține multe cicluri; unul dintre ele pornește de la Audrey, apoi trece pe la Bill, la Emily, Jeff, Harry, Ilana, iar apoi ajunge înapoi la Audrey. Există un ciclu mai scurt care conţine pe Audrey, cel arătat mai jos: Audrey, Bill, Gayle şi înapoi la Audrey. Ce alte cicluri poți găsi?

Uneori, pe muchii avem notate niște valori. De exemplu, în rețeaua socială, am putea folosi valori pentru a indica cât de bine se cunosc cele două persoane. Hai să mai luăm un alt exemplu: să reprezentăm o hartă printr-un graf. Presupunând că nu există străzi cu sens unic, o hartă poate fi privită și ea ca un graf neorientat care are oraşele ca noduri, străzile dintre orașe ca muchii, iar valorile de pe muchii indică distanţa. De exemplu, iată o hartă, nu chiar la scară, a unora dintre autostrăzile interstatale din nord-estul SUA, având distanțele notate pe muchii:

Termenul general pe care îl folosim pentru valorile asociate muchiilor este cost, iar un graf ale cărui muchii au asociate costuri se numește graf ponderat. În cazul unei hărți rutiere, dacă vrei să găsești cea mai scurtă rută dintre două localități, cauți acel drum care are suma costurilor muchiilor minimă. La fel ca în cazul grafurilor neponderate, numim un astfel de drum cel mai scurt. De exemplu, în acest graf, cel mai scurt drum de la New York la Concord pornește din New York, apoi trece prin New Haven, Hartford, Sturbridge, Weston, Reading și în final ajunge în Concord, având 289 de mile.

Relaţia dintre noduri nu are loc întotdeauna în ambele sensuri. Într-o hartă, de exemplu, ar putea exista străzi cu sens unic. Un alt exemplu: avem un graf care arată ordinea în care se poate îmbrăca un portar de hochei de gheaţă:

În acest caz, muchiile conțin săgeți și sunt orientate; spunem că avem un graf orientat. Aici, sensul de pe săgeți arată ce piese de echipament trebuie puse înaintea altor piese. De exemplu, arcul dintre chest pad (protecția pentru piept) și sweater (pulover) indică faptul că protecția trebuie pusă înaintea puloverului. Numerele de lângă vârfuri indică o eventuală ordine a pieselor de echipament, astfel încât undershorts (chilotul) să fie primul, apoi socks (șosetele), compression shorts (colanții) și așa mai departe, cu blocker (apărătoarea) care se pune la final. Probabil că ai observat că acest graf orientat nu are cicluri; noi numim un astfel de graf graf orientat aciclic sau goa. Desigur, putem avea grafuri orientate ponderate, cum ar fi hărțile cu străzi cu sens unic și distanțe rutiere.

Pentru grafurile orientate avem o terminologie specifică. Spunem că o muchie orientată (arc) pornește dintr-un vârf şi intră în celălalt. De exemplu, din vârful care reprezintă apărătoarea pentru piept pornește un arc care intră în vârful corespunzător puloverului. Dacă un arc pornește din vârful $u$u și intră în vârful $v$v, îl notăm cu $(u, v)$left parenthesis, u, comma, v, right parenthesis, și evidențiem faptul că ordinea vârfurilor în pereche este importantă. Numărul de arce care pornesc dintr-un vârf reprezintă gradul extern, iar numărul de arce care intră reprezintă gradul intern.

După ți-ai imaginat deja, grafurile - atât cele orientate cât și cele neorientate - au multe aplicații în modelarea relațiilor din lumea reală.

Când lucrăm cu grafuri, este foarte util să putem vorbi despre mulțimea nodurilor (vârfurilor) și mulțimea muchiilor (arcelor). De obicei, se notează mulțimea vârfurilor cu $V$V și mulțimea arcelor cu $E$E. Când reprezentăm un graf sau când analizăm un algoritm pentru un graf, folosim numărul de vârfuri și cardinalul mulțimii arcelor în notația asimptotică. De exemplu, să presupunem că vrem să vorbim despre timpul de execuție care este liniar în funcție de numărul de vârfuri. Strict vorbind, ar trebui să zicem că este $\Theta(|V|)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis, folosind notația $|\cdot|$vertical bar, dot, vertical bar pentru numărul de elemente dintr-o mulțime (cardinalul mulțimii). Dar în această manieră notația asimptotică este greoaie. Deci, vom adopta convenția ca în notație asimptotică, și doar în notație asimptotică, când scriem mulțimea ea să reprezinte, de fapt, cardinalul său. Deci, în loc să scriem $\Theta(|V|)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis, scriem doar $\Theta(V)$\Theta, left parenthesis, V, right parenthesis. În mod similar, în loc de $\Theta(\lg |E|)$\Theta, left parenthesis, \lg, vertical bar, E, vertical bar, right parenthesis, scriem $\Theta(\lg E)$\Theta, left parenthesis, \lg, E, right parenthesis.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.