Introducere în teoria grafurilor

Un graf $G = (V, E)$ este o structură matematică compusă din două mulțimi:

• $V$ (mulțimea vârfurilor sau nodurilor), care reprezintă obiectele;

• $E \subseteq V \times V$ (mulțimea muchiilor sau arcelor), care reprezintă legăturile între perechi de vârfuri.

Fiecare element $v \in V$ este numit vârf (sau nod), iar fiecare element $e = (u, v) \in E$ este numit muchie (sau arc). În mod obișnuit, grafurile sunt reprezentate grafic printr-un set de puncte (corespunzătoare vârfurilor) conectate prin linii sau curbe (corespunzătoare muchiilor).

Un graf neorientat $G = (V, E)$ este un graf în care perechile de vârfuri $(u, v) \in E$ sunt neordonate. Aceasta înseamnă că, dacă $(u, v)\in E$ este o muchie de la $u$ la $v$, atunci și $(v, u) \in E$.

Prin comparație, un graf orientat este un graf în care perechile de vârfuri $(u, v) \in E$ sunt ordonate. Aceasta înseamnă că, dacă $(u, v) \in E$, atunci $(v, u) \not\in E$.

Două noduri $u$ și $v$ sunt adiacente în graful $G = (V, E)$ dacă există o muchie $(u, v) \in E$. Adică, există o legătură directă între $u$ și $v$.

Formal:

Folosim noțiunea de incidență pentru a descrie relația dintre noduri și muchii. O muchie $(u, v) \in E$ este incidentă cu nodurile $u$ și $v$.

Definim gradul unui nod $v$ dintr-un graf $G = (V, E)$ ca fiind numărul de muchii incidente cu $v$.

Într-un graf neorientat $G = (V, E)$:

$\sum_{v \in V} \deg(v) = 2k,\,k \in \mathbb{N}$

Numim lanț o secvență de noduri $(v_1, v_2, ..., v_k)$ cu proprietatea că $(v_i, v_{i + 1}) \in E$ oricare ar fi $1 \leq i \leq k$. Un lanț este -elementar* dacă $v_i \neq v_j$ oricare ar fi $1 \leq i < j \leq k$. Un lanț este simplu dacă $(v_i, v_{i + 1}) \neq (v_j, v_{j+1})$ oricare ar fi $1 \leq i < j \leq k$.

O secvență de muchii $(v_1, v_2, ..., v_k, v_1)$ formează un ciclu dacă $(v_i, v_{i + 1}) \in E$ pentru orice $1 \leq i < k$ și $(v_k, v_1) \in E$. Un ciclu este simplu dacă $v_i \neq v_j$ pentru orice $1 \leq i < j < k$.

Lungimea unui lanț $(v_1, v_2, ..., v_k)$ este $k-1$ (numărul de muchii). Uneori, aceasta se definește ca fiind numărul de noduri, așadar lungimea acestui lanț este $k$.

Definim graf parțial al unui graf dat ca fiind ceea ce rămâne din graful dat păstrând toate nodurile și eliminând eventual unele muchii, fără a adăuga muchii noi.

Formal spus, un graf parțial $G' = (V, E')$ a grafului $G = (V, E)$ este un graf unde $E' \subseteq E$.

Definim subgraf al unui graf dat ca fiind ceea ce rămâne din graful dat eliminând unele noduri și doar muchiile incidente lor, deci nu și alte muchii și fără să adăugăm alte muchii.

Formal spus, un subgraf $G' = (V', E')$ al unui graf $G = (V, E)$ este un graf unde $V' \subseteq V$ și $E' \subseteq \{(u, v) \in E \mid u, v \in V'\}$.

Numărul de subgrafuri ale unui graf $G = (V, E)$ este $2^{|V|}$, iar numărul de grafuri parțiale este $2^{|E|}$, unde $|V| = n$ este numărul de noduri, iar $|E| = m$ este numărul de muchii al grafului.

Definim un graf complet $K_n = (V, E)$ cu $|V| = n$ ca fiind un graf unde $(v_i, v_j) \in E\ \forall 1 \leq i < j \leq n$. Altfel spus, fiecare nod este conectat cu toate celelalte noduri.

Numărul de muchii ale unui graf complet $K_n$ este $|E| = \frac{n(n-1)}{2}$.

Definim un graf bipartit $G = (A, B, E)$ ca fiind un graf care poate fi împărțit în două submulțimi $V = A \cup B$ cu $A \cap B = \emptyset$, astfel încât, dacă $a \in A$, atunci acesta se poate conecta doar cu $b \in B$ și viceversa.

Are loc următoarea relație pentru un graf bipartit $G = (A, B, E)$: $\sum_{a \in a} \deg(a) = \sum_{b \in B} \deg(b) = |E|$

Un graf este bipartit dacă și numai dacă acesta nu conține un ciclu de lungime impară.

Definim un graf planar ca fiind un graf care are proprietatea că poate fi reprezentat grafic fără ca două muchii să se intersecteze.

Un graf regulat $G = (V, E)$ este un graf în care $\deg(v) = k\ \forall v \in V$. Adică, fiecare nod din graf are același număr de muchii incidente.

Un graf regulat cu nodurile de gradul $k$ se numește graf $k$-regulat.

Condiția necesară și suficientă pentru ca un graf $k$-regulat de ordin $n$ să existe este ca $n \geq k + 1$ și că $nk$ este par.

Definim matricea de adiacență a unui graf ca fiind o matrice binară pentru care $a_{ij} = 1$ dacă și numai dacă avem muchie de la nodul $i$ la nodul $j$ și $a_{ij} = 0$ în caz contrar.

Pentru un graf neorientat, matricea este mereu simetrică, adică $a_{ij} = a_{ji}\ \forall i, j$.

Definim o listă de vecini ca fiind o listă (de regulă, alocată dinamic) pe care o folosim pentru a ține în memorie pentru fiecare nod doar nodurile adiacente cu acesta, această metodă fiind cea mai eficientă din punct de vedere practic pentru a parcurge grafurile.

Pentru graful de mai sus, aceasta este lista de vecini:

Definim o listă de muchii ca fiind o listă pe care o folosim pentru a ține toate muchiile în memorie. Deși nu este o variantă prea practică de a efectua parcurgerile, această metodă poate fi utilă pentru anumiți algoritmi ce se bazează în principal pe prelucrarea muchiilor, un astfel de exemplu fiind arborele parțial de cost minim.

În cazul nostru, lista de muchii este: $\{1, 4\}$, $\{1, 3\}$, $\{4,9\}$, $\{9,3\}$, $\{4,2\}$, $\{4,6\}$, $\{2,6\}$, $\{2,5\}$, $\{8,12\}$, $\{8,11\}$, $\{8,10\}$, $\{8,7\}$.

Un graf conex este un graf neorientat în care există o cale între oricare două noduri. Cu alte cuvinte, oricare două noduri din graf sunt conectate direct sau indirect printr-o serie de muchii.

O componentă conexă a unui graf este un subgraf conex maximal, adică un subgraf în care oricare două noduri sunt conectate printr-o serie de muchii, iar acest subgraf nu poate fi extins adăugând vreun alt nod sau vreo altă muchie fără a pierde proprietatea de conexitate.

Parcurgerea în adâncime (DFS) este un algoritm de explorare a grafului care începe de la un nod ales și vizitează cât mai mult posibil din vecinii acestuia înainte de a se întoarce înapoi. Aceasta se realizează printr-o strategie de backtracking recursivă sau prin utilizarea unei stive (stack).

DFS începe de la un nod și vizitează toate nodurile pe care le poate atinge în adâncime înainte de a reveni la nodurile anterioare și verifică dacă un nod a fost deja vizitat pentru a evita bucle infinite.

Complexitatea parcurgerii în adâncime (DFS) este $\mathcal{O}(\lvert V \rvert + \lvert E \lvert)$, unde $\lvert V \rvert$ reprezintă numărul de noduri sau vârfuri și $\lvert E \rvert$ reprezintă numărul de muchii.

În probleme se notează convențional $\lvert V \rvert$ cu $N$ de la noduri, respectiv $\lvert E \rvert$ cu $M$ de la muchii.

Se remarcă faptul că un nod va fi vizitat la un moment dat doar o singură dată, deci dacă avem muchiile $(1, 2)$, $(1, 3)$ și $(2, 3)$, iar DFS-ul pleacă din 1, 2 va fi accesat din 1, iar 3 va fi accesat din 2.

Se poate remarca faptul că ordinea în care vizităm nodurile în graf depinde de ordinea în care sunt adăugate muchiile în graf, acest lucru înseamnă că nu putem folosi DFS pentru anumite probleme, de exemplu cele la care trebuie aflată distanța minimă în graf.

Un drum minim este lungimea minimă a unui lanț care leagă două noduri din graf.

Parcurgerea în lățime** (BFS, engl. breadth-first search) a unui graf ca fiind o parcurgere iterativă ce pleacă de la unul sau mai multe noduri, iar la fiecare pas, dacă ne aflăm la un nod $x$, vom vizita vecinii nevizitați ai nodului $x$, adăugându-i într-o coadă, nodurile fiind parcurse în ordinea în care au fost adăugate în coadă.

Complexitatea parcurgerii în lățime (BFS) este $\mathcal{O}(\lvert V \rvert + \lvert E \lvert)$, unde $\lvert V \rvert$ reprezintă numărul de noduri sau vârfuri și $\lvert E \rvert$ reprezintă numărul de muchii.

Se poate remarca faptul că ordinea în care vizităm nodurile în graf va fi aceeași cu ordinea crescătoare a distanței minime față de nodul sau nodurile inițiale, datorită faptului că ele vor fi inserate în coadă în ordinea în care acestea au fost adăugate.