Teorie

Grafuri și arbori la atestatul de informatică — matricea de adiacență, grade, vectorul de tați, în C++

Matricea de adiacență construită din lista de muchii, gradul unui nod ca sumă pe linie, graful orientat (grad interior și exterior), nodurile izolate, numărul de muchii și arborele dat prin vectorul de tați — cu problemele de atestat în care apar.

minute de citit

secțiuni

probleme rezolvate legate

Actualizat pe 25 octombrie 2026.

Pe această pagină

Matricea de adiacență
Tehnica 1 — Gradul unui nod: suma liniei
Tehnica 2 — Graful orientat: linia pleacă, coloana sosește
Tehnica 3 — Numărul de muchii
Tehnica 4 — Arborele dat prin vectorul de tați
Greșeli care se repetă
Unde exersezi mai departe
Toate problemele din această categorie

Grafurile apar la atestat într-o formă mult mai blândă decât la bacalaureat: în cele șase probleme din sesiunea Bucureşti 2020 nu se cer parcurgeri (BFS, DFS) și nici drumuri minime. Toate se reduc la două reprezentări — matricea de adiacență și vectorul de tați — și la o singură idee: gradul unui nod e o sumă pe o linie a matricei.

Fiecare problemă vine, ca de obicei la atestat, cu un subprogram cerut la punctul a) (suma_x, linie_x, pozitie, nrElem1), iar programul de la final trebuie să-l folosească. Subprogramul e aproape mereu o operație simplă pe vectori sau matrici; partea de grafuri e să știi ce linie îi dai.

Matricea de adiacență

Un graf cu n noduri, etichetate 1 … n, se memorează într-o matrice n × n: a[i][j] = 1 dacă există muchie între i și j, altfel 0. Fișierul nu dă matricea, ci lista muchiilor, iar numărul lor nu se spune — se citesc până la sfârșitul fișierului:

C++

int a[100][100];                       // globala: porneste plina de zerouri

int main() {
    ifstream f("grade.in");
    int n, x, y;
    f >> n;
    while (f >> x >> y)
        a[x][y] = a[y][x] = 1;         // graf neorientat: ambele sensuri
}

Trei detalii decid corectitudinea:

La graful neorientat, muchia se marchează în ambele sensuri. Matricea iese simetrică față de diagonala principală. Marcată într-un singur sens, nodul 5 din muchia 2 5 ar avea gradul 0.
= 1, nu ++. Dacă aceeași muchie apare de două ori în fișier, ++ o numără de două ori.
Matricea globală sau inițializată (= {}). Una locală neinițializată conține valori oarecare.

Unele subiecte dau direct matricea (n linii de câte n valori 0/1) — atunci se citește ca orice matrice din fișier.

Exersează pe subiecte reale

nodurile de grad maxim și cele izolate nodurile izolate, din matricea dată

Tehnica 1

Gradul unui nod: suma liniei

Gradul nodului i (câte muchii pleacă din el) e numărul de valori 1 de pe linia i — adică suma liniei. Subprogramul cerut la a) e exact funcția asta, sub diverse nume:

C++

int suma_x(int n, int a[][100], int x) {
    int s = 0;
    for (int j = 1; j <= n; j++) s += a[x][j];
    return s;
}

Din grad ies toate cerințele obișnuite, cu tiparele de la vectori:

Cerința	Cum
nodurile de grad maxim	maximul gradelor, apoi a doua parcurgere care le afișează pe cele egale cu el
nodurile izolate	gradul `0` — linia plină de zerouri
„sau mesajul nu exista”	un flag setat la primul nod găsit

Când subprogramul primește un tablou unidimensional (suma(v, k), nrElem1(n, v, s)), îi dai linia direct: a[i] e ea însăși un vector cu n elemente, deci suma(a[i], n) e gradul nodului.

Exersează pe subiecte reale

grad maxim și noduri izolate nodurile izolate, cu suma(a[i], n)

Tehnica 2

Graful orientat: linia pleacă, coloana sosește

Într-un graf orientat, legăturile sunt arce cu sens: x → y. Se marchează doar a[x][y] = 1, iar matricea nu mai e simetrică. Fiecare vârf are acum două grade:

gradul exterior — câte arce pleacă — valorile nenule de pe linia vârfului;
gradul interior — câte arce sosesc — valorile nenule de pe coloana lui.

C++

int coloana_x(int n, int a[][100], int x) {   // grad interior
    int c = 0;
    for (int i = 1; i <= n; i++)
        if (a[i][x] != 0) c++;
    return c;
}

Regula de memorat: linia = de unde pleacă, coloana = unde ajunge, exact ca în a[x][y] pentru x → y. Inversate, gradele se schimbă între ele — la o cerință de tipul „gradul interior egal cu cel exterior” nu se vede, la „gradul exterior maxim” rezultatul iese greșit.

Exersează pe subiecte reale

vârfurile cu gradul interior egal cu cel exterior

Tehnica 3

Numărul de muchii

Suma tuturor gradelor numără fiecare muchie de două ori — o dată din fiecare capăt. De aceea:

Graf	Numărul de muchii / arce
neorientat	suma tuturor elementelor matricei / 2
orientat	suma gradelor exterioare (fiecare arc pleacă din exact un vârf) — fără împărțire

Numărul de muchii nu e numărul de linii citite din fișier: o muchie scrisă de două ori apare o singură dată în matrice.

Aceeași idee rezolvă și cerința „eliminați nodurile de grad minim și numărați muchiile rămase”: eliminarea unui nod înseamnă zerorizarea liniei și a coloanei lui, apoi suma matricei împărțită la 2. Detaliul care contează e ordinea: marchezi întâi toate nodurile de grad minim, după gradele inițiale, și abia apoi le elimini. Recalculând minimul după fiecare eliminare, scoți alte noduri decât cele cerute.

C++

for (int i = 0; i < n; i++) sters[i] = (grad[i] == minim);   // intai marcam
for (int i = 0; i < n; i++)
    if (sters[i])
        for (int j = 0; j < n; j++) a[i][j] = a[j][i] = 0;    // apoi eliminam
cout << sumaElem(n, a) / 2;

Exersează pe subiecte reale

numărul de arce eliminarea nodurilor de grad minim

Tehnica 4

Arborele dat prin vectorul de tați

Un arbore cu rădăcină se dă printr-un singur vector: t[i] = tatăl (părintele) nodului i. Rădăcina e singurul nod fără tată, deci singurul cu t[i] = 0.

nodul:  1  2  3  4  5  6  7  8  9  10
t[i]:   2  0  2  2  3  3  5  3  1  1      ->  radacina = 2

Toate cerințele se reduc la întrebări despre aparițiile valorilor în t:

Cerința	Întrebarea	Cod
rădăcina	pe ce poziție e `0`?	`pozitie(n, t, 0)`
câți fii are `i`	de câte ori apare valoarea `i` în `t`?	vector de frecvență: `fii[t[i]]++` la citire
e `i` frunză?	apare `i` în `t`?	`pozitie(n, t, i) == -1`
matricea de adiacență	fiecare nod cu tată dă muchia `i – t[i]`	`a[i][t[i]] = a[t[i]][i] = 1`

Rădăcina nu e mereu nodul 1 — în exemplul de mai sus e 2. Se caută, nu se presupune.

Exersează pe subiecte reale

rădăcina, nodurile cu cei mai mulți fii, frunzele rădăcina și matricea de adiacență din vectorul de tați

Greșeli care se repetă

Muchia marcată într-un singur sens la graful neorientat — grade greșite, matrice nesimetrică
Arcul marcat în ambele sensuri la graful orientat — toate vârfurile ajung cu gradele egale
a[x][y]++ în loc de = 1 — o muchie repetată în fișier se numără de două ori
Matrice locală neinițializată — valori aleatorii acolo unde nu e muchie
Citirea unui număr fix de muchii — fișierul nu spune câte sunt; while (f >> x >> y)
Suma matricei neîmpărțită la 2 — numărul de muchii iese dublu
Etichete de la 0 când matricea e indexată de la 0 — se afișează i + 1
Linie și coloană inversate la gradul interior / exterior
Rădăcina presupusă 1 — se caută poziția lui 0 în vectorul de tați
Subprogramul de la a) nefolosit în programul final — rezultatul poate fi corect, dar enunțul cere „apeluri utile” și se punctează separat

Mai departe

Unde exersezi mai departe

Grafurile de la atestat sunt, în fond, exerciții pe matrici. Dacă tiparele de mai sus îți sunt străine, începe cu matricile — parcurgerea pe linii și pe coloane e aceeași.

Pentru mai mult, pbinfo.ro are probleme de grafuri cu evaluator automat, de la gradele nodurilor până la parcurgeri — utile mai ales dacă dai și bacalaureatul.

Toate problemele din această categorie

Fiecare are rezolvare completă în C++, explicată pas cu pas.

6Arată toate problemele rezolvate6 programare

Alte pagini de teorie

Sortare și ordonare în C++21 Baze de date în Access90 Baze de date şi SQL81 Date structurate8 Lucrul cu fișiere în C++90 Formatarea documentelor Word39 Formule și funcții Excel51 Interogări SQL pe două tabele91 Matrici51 Modelul entitate-relație25 Numere și divizibilitate127 Prezentări PowerPoint23 Recursivitate în C++6 Șiruri de caractere38 Șiruri recurente7 Sisteme de operare41 Vectori59