Grad

Intuiția

Gradul unui nod îți spune cât de „conectat" este acel nod: câte legături pleacă din el. Un nod izolat are gradul 0; un nod foarte popular are gradul mare. La grafurile orientate distingem două direcții: câte legături intră și câte ies — la fel cum o persoană poate urmări mulți oameni, dar are puțini care o urmăresc pe ea.

Vezi cum funcționează

Pornește animația. Vizualizatorul se plimbă pe rând prin fiecare nod, aprinde muchiile incidente cu el și îți arată gradul calculat — exact numărul de muchii pe care le-a aprins.

Ce este

Într-un graf neorientat, gradul unui nod v, notat d(v), este numărul de muchii incidente cu v (muchiile care au pe v drept capăt). O buclă (muchie de la v la v) contribuie cu +2, fiindcă atinge nodul de două ori.

Două tipuri de noduri primesc nume speciale, după grad:

• nod izolat — grad 0: nu îl atinge nicio muchie (invitatul care nu cunoaște pe nimeni la petrecere);
• nod terminal — grad 1: e legat de o singură muchie (capătul unui fir).

Într-un graf orientat, fiecare arc are o direcție, deci separăm:

• gradul interior d⁻(v) = numărul de arce care intră în v;
• gradul exterior d⁺(v) = numărul de arce care ies din v.

Evident, d⁻(v) + d⁺(v) dă numărul total de arce incidente cu v.

Există o relație care leagă gradele de numărul de muchii — lema strângerii de mână: într-un graf neorientat, suma gradelor tuturor nodurilor este de două ori numărul de muchii:

$\sum_{v} d(v) = 2 \cdot |E|$

Motivul e simplu: fiecare muchie are exact două capete, deci e numărată o dată în gradul fiecăruia — adică de două ori în total. La grafuri orientate, fiecare arc adaugă +1 la un grad exterior și +1 la un grad interior, deci suma gradelor interioare egalează suma gradelor exterioare, ambele egale cu |E|.

Cum arată

Ia graful neorientat cu 6 noduri și muchiile {0,1}, {0,2}, {1,2}, {2,3}, {3,4}, {3,5}. Calculăm gradul fiecărui nod numărând în câte muchii apare:

Verificăm lema strângerii de mână: suma gradelor este 2 + 2 + 3 + 3 + 1 + 1 = 12, iar graful are 6 muchii, deci 2 · 6 = 12. Se potrivește — și numărăm 4 noduri de grad impar (nodurile 2, 3, 4, 5), număr par, exact cum prezice observația. Nodurile 4 și 5 sunt terminale (grad 1); graful nu are niciun nod izolat — dar dacă am șterge muchia {3,4}, nodul 4 ar rămâne cu gradul 0, izolat.

Lema ca instrument de demonstrație

Implementare C++

Citim lista de muchii și calculăm gradele numărând incidențele. La final verificăm lema strângerii de mână.

#include <iostream>
using namespace std;

int grad[100];    // grad[v] = gradul nodului v

int main() {
    int n, m;
    cin >> n >> m;            // n noduri, m muchii

    long long suma = 0;
    for (int e = 0; e < m; e++) {
        int u, v;
        cin >> u >> v;
        // muchie neorientata: contribuie +1 la fiecare capat
        grad[u]++;
        grad[v]++;
        suma += 2;            // fiecare muchie adauga 2 la suma gradelor
    }

    for (int v = 0; v < n; v++)
        cout << "grad(" << v << ") = " << grad[v] << "\n";

    // verificarea lemei strangerii de mana: suma == 2 * m
    cout << "suma gradelor = " << suma << " = 2 * " << m << "\n";
    // pentru graful exemplu (6 noduri, 6 muchii): suma gradelor = 12

    return 0;
}

Pentru un graf orientat ținem doi vectori separați: la fiecare arc u -> v creștem gradul exterior al lui u și gradul interior al lui v.

int gradIn[100];     // grad interior: arce care intra
int gradOut[100];    // grad exterior: arce care ies

void adaugaArc(int u, int v) {
    gradOut[u]++;    // un arc iese din u
    gradIn[v]++;     // si intra in v
}

Iar dacă graful e dat prin matrice de adiacență a[][] (formatul clasic de la subiectele de bacalaureat), gradul nodului v este pur și simplu suma liniei v:

// grad[v] = numarul de 1 de pe linia v din matricea de adiacenta
for (int u = 0; u < n; u++)
    grad[v] += a[v][u];