Graful neorientat

Un graf neorientat are o mulțime de vârfuri și muchii care leagă perechi de vârfuri fără sens de parcurgere impus. Pentru vârfurile $\{1;2;3\}$ și muchiile $[1;2]$, $[2;3]$, vârful 1 este vecin cu 2, dar nu direct cu 3. Într-un graf simplu nu există bucle sau muchii multiple.

Un graf neorientat este o pereche formată dintr-o mulțime de vârfuri și o mulțime de muchii; fiecare muchie $[x,y]$ leagă două vârfuri și nu are sens de parcurgere, deci $[x,y]$ și $[y,x]$ sunt aceeași muchie. Două vârfuri sunt adiacente (vecine) dacă există o muchie între ele. O muchie este incidentă cu fiecare dintre cele două extremități ale sale: $[1,2]$ este incidentă cu 1 și cu 2, dar nu cu 3. Un graf simplu nu are bucle (muchii de forma $[x,x]$) și nici muchii multiple. La Bac și la admitere grafurile sunt simple, cu vârfurile numerotate de la 1 la $n$.

Exemplul 1 — matricea de adiacență. Citim $n$ vârfuri și $m$ muchii și construim matricea simetrică:

#include <iostream>
using namespace std;
int main() {
    int n, m, a[11][11] = {};
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            cout << a[i][j] << (j == n ? '\n' : ' ');
    }
}

Programul presupune $1\le n\le 10$, vârfuri numerotate de la 1 la $n$ și muchii valide. Pentru intrarea 3 2, 1 2, 2 3 pe linii succesive, programul afișează 0 1 0, 1 0 1, 0 1 0, fiecare pe rândul ei. Prima muchie pune 1 atât în a[1][2], cât și în a[2][1]; a doua completează pozițiile a[2][3] și a[3][2]. Suma liniei 2 este gradul său, adică 2. La un vârf izolat, linia și coloana sunt numai zerouri, iar diagonala principală conține numai zerouri, pentru că nu există bucle.

Exemplul 2 — listele de adiacență. Pentru fiecare vârf se păstrează lista vecinilor lui. Graful cu 5 vârfuri și muchiile $[1,2]$, $[1,3]$, $[2,3]$, $[3,4]$ se memorează astfel:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n = 5, e[4][2] = {{1, 2}, {1, 3}, {2, 3}, {3, 4}};
    vector<int> v[6];
    for (auto& m : e) {
        v[m[0]].push_back(m[1]);
        v[m[1]].push_back(m[0]);
    }
    for (int i = 1; i <= n; ++i) {
        cout << i << ":";
        for (int x : v[i]) cout << " " << x;
        cout << "\n";
    }
}

Se afișează 1: 2 3, 2: 1 3, 3: 1 2 4, 4: 3 și 5: (vârful 5 este izolat, deci lista lui e goală). Fiecare muchie apare în două liste, deci listele conțin în total $2m=8$ elemente. Pentru $n$ vârfuri și $m$ muchii, listele ocupă $O(n+m)$ spațiu, iar matricea ocupă $O(n^2)$. Construirea matricei prin citirea muchiilor cere $O(n^2+m)$ cu inițializarea, iar afișarea ei cere încă $O(n^2)$. Matricea răspunde în timp constant la întrebarea „există muchia $[x,y]$?”, în timp ce lista trebuie parcursă. Gradul unui vârf este suma liniei lui în matrice sau lungimea listei lui de vecini; în exemplu, gradele sunt $2,2,3,1,0$.

Exemplul 3 — gradele din lista muchiilor. Gradul unui vârf este numărul muchiilor incidente cu el. Pentru graful cu cinci vârfuri și muchiile $[1,2]$, $[1,3]$, $[2,3]$, $[3,4]$, fiecare muchie $[x,y]$ mărește cu 1 gradul lui $x$ și gradul lui $y$:

int n = 5, e[4][2] = {{1, 2}, {1, 3}, {2, 3}, {3, 4}}, g[6] = {};
for (auto& m : e) { ++g[m[0]]; ++g[m[1]]; }
for (int i = 1; i <= n; ++i) cout << g[i] << ' ';

Se afișează 2 2 3 1 0. Suma gradelor este $2+2+3+1+0=8=2m$, pentru că fiecare muchie este numărată de două ori, câte o dată la fiecare extremitate. Rezultă că suma gradelor este întotdeauna pară, deci numărul vârfurilor cu grad impar este par; în exemplu, vârfurile 3 și 4 au grad impar. Un șir de grade cu suma impară, de pildă $1,2,2,2,2$, nu poate aparține niciunui graf.

Cazul-limită: graful complet. Într-un graf complet cu $n$ vârfuri fiecare vârf este adiacent cu toate celelalte, deci toate gradele sunt egale cu $n-1$, iar numărul muchiilor este $n(n-1)/2$. Pentru $n=5$ sunt 10 muchii și gradul 4 pentru fiecare vârf; suma gradelor este $5\cdot 4=20=2\cdot 10$.

Sunt $C_n^2=n(n-1)/2$ perechi distincte de vârfuri. Pentru fiecare pereche alegem independent dacă există sau nu muchia, astfel numărul grafurilor simple neorientate cu mulțimea fixată a celor $n$ vârfuri este $2^{C_n^2}$. Pentru $n=3$, cele trei perechi dau $2^3=8$ grafuri distincte; pentru $n=4$ sunt $2^6=64$. O muchie $[u,v]$ se numără o singură dată, deși matricea conține două valori simetrice. De aceea numărul valorilor 1 din matricea de adiacență este $2m$, iar suma tuturor elementelor este un număr par. Matricea unui graf simplu neorientat este simetrică față de diagonala principală, iar pe diagonală are zerouri; dacă într-un enunț apare un 1 pe diagonală sau o matrice nesimetrică, nu este vorba de un graf simplu neorientat.

Exemplu în formatul examenului. Un graf neorientat cu 5 vârfuri are muchiile $[1,2]$, $[1,3]$, $[2,3]$ și $[3,4]$. Câte elemente egale cu 1 are matricea lui de adiacență?

• a) 4
• b) 8
• c) 10
• d) 25

Răspunsul corect este b). Graful are $m=4$ muchii, iar fiecare muchie $[x,y]$ pune 1 în două poziții, a[x][y] și a[y][x]. Rezultă $2\cdot 4=8$ elemente egale cu 1. Varianta a) numără muchiile o singură dată, deci ignoră simetria matricei. Varianta c) este numărul perechilor posibile de vârfuri, $C_5^2=10$, nu al muchiilor existente, iar d) este numărul tuturor elementelor matricei, $5\cdot 5$, nu al celor egale cu 1. Verificare pe linii: sumele celor cinci linii sunt gradele $2$, $2$, $3$, $1$, $0$, iar $2+2+3+1+0=8$.

Greșeli frecvente

• Greșit: muchia $\{1,2\}$ și $\{2,1\}$ sunt două muchii distincte.
  Corect: într-un graf neorientat sunt aceeași muchie.
• Greșit: 1 și 3 sunt vecine în exemplu.
  Corect: sunt legate prin 2, dar nu au muchie directă.
• Greșit: orice graf are toate perechile de vârfuri conectate direct.
  Corect: asta caracterizează doar un graf complet.

Înainte și după