Grafuri neorientate: grade, muchii și conexitate

Gradul $d(v)$ este numărul de muchii incidente vârfului $v$. O muchie cu extremitățile $u$ și $v$ contribuie cu 1 la fiecare dintre cele două grade. Pentru $m$ muchii:

$\sum_{v\in V} d(v)=2m.$

Consecințe: suma gradelor este pară, iar numărul vârfurilor de grad impar este par. Un vârf izolat are gradul 0.

Pentru un graf simplu cu $n$ vârfuri, fiecare grad este între 0 și $n-1$. Aceste condiții sunt necesare, dar nu suficiente pentru ca o listă de numere să fie lista gradelor unui graf. De exemplu, $3,3,1,1$ are sumă pară și toate valorile cel mult 3, dar nu se poate realiza: fiecare dintre cele două vârfuri de grad 3 ar trebui să se lege de ambele vârfuri care au gradul 1.

În graful complet $K_n$, fiecare pereche de vârfuri distincte este legată printr-o muchie. Fiecare grad este $n-1$, iar numărul de muchii este:

$m_{\max}=\frac{n(n-1)}{2}.$

În matricea de adiacență, $a_{ij}=1$ dacă există muchia dintre $i$ și $j$, altfel $a_{ij}=0$. Pentru un graf simplu neorientat, matricea este simetrică și diagonala este nulă.

Suma liniei $i$ este gradul vârfului $i$. Suma întregii matrice este $2m$. Dacă numeri doar elementele de deasupra diagonalei principale, obții direct $m$. Nu împărți încă o dată la 2.

Un graf este conex dacă între oricare două vârfuri există un lanț. O componentă conexă este o parte maximală în care vârfurile sunt legate între ele prin lanțuri.

Un graf conex cu $n$ vârfuri are cel puțin $n-1$ muchii. Totuși, $m\geq n-1$ nu garantează conexitatea. Un triunghi și un vârf izolat au $n=4$ și $m=3$, dar graful este neconex.

Un arbore este un graf conex fără cicluri. El are $n-1$ muchii. Pentru un graf simplu neorientat cu $n\geq1$, dacă știi că este conex și are exact $n-1$ muchii, poți concluziona că este arbore.

Pentru verificarea conexității poți porni o parcurgere dintr-un vârf și marca toate vârfurile accesibile. Dacă rămân nemarcate, graful are mai multe componente.

Dacă graful are $c$ componente conexe, sunt necesare și suficiente $c-1$ muchii noi ca să-l faci conex. Fiecare muchie între două componente poate reduce numărul componentelor cu cel mult 1.

Pentru a atinge limita, alegi câte un vârf din fiecare componentă și legi componentele într-un lanț. O muchie adăugată între două vârfuri din aceeași componentă nu ajută la unirea cu restul grafului.

La implementare, listele de adiacență ocupă $O(n+m)$ memorie, iar matricea ocupă $O(n^2)$. Alegerea reprezentării influențează complexitatea algoritmului.

Un graf simplu neorientat are vârfurile $1,2,3,4,5,6$ și muchiile $\{1,2\}$, $\{2,3\}$, $\{1,3\}$, $\{4,5\}$. Determină gradele, componentele conexe și numărul minim de muchii care trebuie adăugate pentru a obține un graf conex.

Vârfurile 1, 2 și 3 formează un triunghi și au fiecare gradul 2. Vârfurile 4 și 5 sunt legate între ele și au gradul 1. Vârful 6 este izolat, cu gradul 0.

Lista gradelor este $2,2,2,1,1,0$. Suma este 8, adică $2\cdot4$, ceea ce confirmă cele patru muchii.

Componentele sunt $\{1,2,3\}$, $\{4,5\}$ și $\{6\}$. Avem $c=3$, deci sunt necesare 2 muchii. De exemplu, adăugăm $\{3,4\}$ și $\{5,6\}$.

Graful final este conex, dar nu este arbore: triunghiul inițial a rămas, deci există un ciclu.