Capitolul 16 · Lecția 16.3 din 3

Reprezentarea grafurilor: matrice și liste de adiacență

Matricea de adiacență, listele de adiacență și calculul gradelor, în 4 limbaje.

Capitolul 16: Grafuri neorientate

Pe această pagină4 secțiuni

Matricea de adiacență

Pentru un graf cu $n$ noduri, matricea $a$ are $n \times n$ elemente:

$a[i][j] = \begin{cases} 1, & \text{dacă există muchie între } i \text{ și } j \\ 0, & \text{altfel} \end{cases}$

Proprietăți la graf neorientat:

matricea e simetrică: $a[i][j] = a[j][i]$ ;
diagonala principală e formată din zerouri (fără bucle);
gradul nodului $i$ = suma elementelor de pe linia $i$ ;
numărul de muchii = suma tuturor elementelor, împărțită la 2.

Listele de adiacență

Pentru fiecare nod se reține lista vecinilor lui. Ocupă mai puțină memorie când graful are puține muchii (graf rar).

Exemplu rezolvat

Graf cu 4 noduri și muchiile [1,2], [1,3], [2,3], [3,4]:

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

Gradele: $d(1)=2$ , $d(2)=2$ , $d(3)=3$ , $d(4)=1$ . Suma = 8 = 2 × 4 muchii. ✓

Reține

Verificarea rapidă la examen: suma tuturor elementelor din matrice trebuie să fie dublul numărului de muchii. Dacă nu iese, ai greșit undeva.

Greșeli frecvente

Se uită simetria și se completează doar jumătate din matrice.
Se numără muchiile fără să se împartă la 2.
Se pune 1 pe diagonala principală. Un nod nu e adiacent cu el însuși (fără bucle).

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int main() {
    int n, m, a[101][101] = {0};
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int grad = 0;
        for (int j = 1; j <= n; j++) grad += a[i][j];
        cout << "d(" << i << ")=" << grad << " ";
    }
    return 0;
}

Date de intrarese trimit programului la citire

Instrumente pentru lecția asta

Laborator de grafuri

Construiește graful apăsând pe noduri și vezi pe loc matricea de adiacență, listele, gradele și parcurgerile.

Numărul de noduri

Apasă un nod, apoi altul, ca să adaugi sau să scoți muchia dintre ele.

Noduri: 6
Muchii: 5
Suma gradelor: 10
Componente conexe: 2
Conex: nu
Complet: nu

Suma gradelor e 10, adică dublul celor 5 muchii. Nu e o coincidență: fiecare muchie adaugă câte 1 la gradul ambelor capete.

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

Explorează interactiv

Se încarcă instrumentul…

Bifează când ai terminat, ca s-o vezi citită pe toate dispozitivele.

Testează-te pe capitolul 16

Lecția în clipuri

Clipuri scurte, cu voce și subtitrări.