Grafuri neorientate: noduri, muchii, grade și matricea de adiacență

Grafurile neorientate apar la BAC Informatică aproape în fiecare variantă: într-o grilă de la Subiectul I sau într-un item scurt de la Subiectul II. Întrebările sunt de obicei teoretice și se rezolvă cu câteva definiții precise și trei-patru formule. Dacă le ai bine fixate, astfel de itemi sunt puncte sigure. Hai să le luăm pe rând, pe un exemplu concret.

Noțiunile de bază

Un graf neorientat este o pereche G = (V, E), unde V este mulțimea nodurilor (vârfurilor), de obicei numerotate 1, 2, …, n, iar E este mulțimea muchiilor. O muchie este o pereche neordonată de noduri, notată [x, y]: muchia [2, 5] este aceeași cu [5, 2]. La BAC lucrezi cu grafuri fără bucle (muchii de la un nod la el însuși) și fără muchii multiple.

• Două noduri unite printr-o muchie se numesc adiacente.
• O muchie este incidentă cu cele două noduri pe care le unește.
• Gradul unui nod x, notat d(x), este numărul de muchii incidente cu el, adică numărul vecinilor săi.
• Un nod cu gradul 0 este izolat; un nod cu gradul 1 este terminal.

Exemplul cu care lucrăm

Fie graful cu n = 5 noduri și m = 4 muchii: [1,2], [1,3], [2,3], [3,4]. Gradele sunt:

Nodul 5 este izolat, nodul 4 este terminal. Suma gradelor este 2 + 2 + 3 + 1 + 0 = 8, adică exact dublul numărului de muchii. Nu e o coincidență.

Formulele de reținut

1. Suma gradelor

d(1) + d(2) + … + d(n) = 2m. Fiecare muchie [x, y] crește cu 1 atât gradul lui x, cât și gradul lui y, deci contribuie cu 2 la sumă. Consecință directă: numărul nodurilor cu grad impar este întotdeauna par.

Aplicație tipică: un graf cu 6 noduri are gradele 1, 2, 2, 3, 3 și x. Ce valori poate avea x? Suma 11 + x trebuie să fie pară, deci x este impar; în plus, x ≤ 5 (un nod poate avea cel mult n − 1 vecini). Rămân variantele 1, 3 și 5, și pentru fiecare se poate construi efectiv un astfel de graf.

2. Numărul maxim de muchii

Un graf cu n noduri are cel mult n(n−1)/2 muchii: atâtea perechi distincte de noduri există. Graful care le are pe toate se numește graf complet și se notează Kₙ; în el, fiecare nod are gradul n − 1. De exemplu, K₅ are 5·4/2 = 10 muchii.

3. Numărul de grafuri

Pentru n noduri date, fiecare dintre cele n(n−1)/2 muchii posibile poate exista sau nu, deci există 2 la puterea n(n−1)/2 grafuri neorientate distincte. Pentru n = 4: 2⁶ = 64.

Graf parțial și subgraf

Aceste două noțiuni se confundă des și apar frecvent în grile:

• Graful parțial se obține eliminând muchii; nodurile rămân toate. Un graf cu m muchii are 2ᵐ grafuri parțiale (inclusiv graful însuși și cel fără nicio muchie).
• Subgraful se obține eliminând noduri, împreună cu toate muchiile incidente cu ele. Un graf cu n noduri are 2ⁿ − 1 subgrafuri (orice submulțime nevidă de noduri, inclusiv graful însuși).

În exemplul nostru, dacă elimini nodul 3, dispar și muchiile [1,3], [2,3], [3,4]: subgraful rămas are nodurile 1, 2, 4, 5 și o singură muchie, [1,2].

Matricea de adiacență

Matricea de adiacență este un tablou a cu n linii și n coloane în care a[i][j] = 1 dacă există muchia [i, j] și 0 în caz contrar. Pentru exemplul nostru:

     1  2  3  4  5
 1   0  1  1  0  0
 2   1  0  1  0  0
 3   1  1  0  1  0
 4   0  0  1  0  0
 5   0  0  0  0  0

Proprietățile pe care trebuie să le recunoști:

• este simetrică față de diagonala principală: a[i][j] = a[j][i];
• are diagonala principală plină de 0 (nu există bucle);
• suma elementelor de pe linia i (sau de pe coloana i) este gradul nodului i;
• numărul total de valori 1 este 2m.

Dacă o grilă îți dă o matrice nesimetrică sau cu un 1 pe diagonală, aceasta nu poate fi matricea de adiacență a unui graf neorientat.

Construirea matricei în C++

Programul de mai jos citește din fișierul graf.in numărul de noduri, numărul de muchii și apoi muchiile, construiește matricea de adiacență și afișează gradul fiecărui nod:

#include <iostream>
#include <fstream>
using namespace std;

int a[101][101];

int main()
{
    ifstream fin("graf.in");
    int n, m, x, y;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;          // graful e neorientat: marcăm ambele sensuri
    }
    for (int i = 1; i <= n; i++)
    {
        int grad = 0;
        for (int j = 1; j <= n; j++)
            grad = grad + a[i][j];
        cout << "Nodul " << i << " are gradul " << grad << '\n';
    }
    fin.close();
    return 0;
}

Pentru fișierul care conține 5 4 urmat de muchiile din exemplu, programul afișează gradele 2, 2, 3, 1, 0. Cea mai frecventă greșeală aici este să marchezi doar a[x][y], uitând simetricul a[y][x].

Listele de adiacență, pe scurt

O altă reprezentare reține, pentru fiecare nod, lista vecinilor săi: 1: 2, 3; 2: 1, 3; 3: 1, 2, 4; 4: 3; 5: (vidă). Ocupă mai puțină memorie când graful are puține muchii, dar pentru itemii de BAC matricea de adiacență este reprezentarea pe care o vei întâlni cel mai des.