Grafuri și arbori - terminologie, proprietăți și reprezentare

Pentru muchia x y într-un graf neorientat marchezi ambele celule oglindă; gradul unui nod este numărul de 1 de pe linia sa:

a[x][y] = 1;
a[y][x] = 1;
// gradul nodului i:
int g = 0;
for (int j = 0; j < n; j++) {
    if (a[i][j] == 1) {
        g++;
    }
}

Un graf se memorează fie prin matricea de adiacență (a[i][j] = 1 dacă există muchie, simplu de interogat, dar ocupă $n^2$ celule), fie prin liste de adiacență (pentru fiecare nod, lista vecinilor lui, economică atunci când muchiile sunt puține).

Gradul unui nod numără TOATE valorile de 1 de pe linia sa, nu doar jumătate (j < i greșește). Și nu uita: a[i][i] = 0, diagonala nu contribuie la grad.

Un lanț este o succesiune de noduri adiacente două câte două; este elementar dacă niciun nod nu se repetă. Un ciclu este un lanț care se închide în nodul de plecare. Lungimea se numără mereu în MUCHII, deci un lanț cu 4 noduri are lungimea 3.

Conex: între oricare două noduri există lanț. Complet: oricare două noduri distincte sunt unite de o muchie, deci are $\frac{n(n-1)}{2}$ muchii. Hamiltonian: are un ciclu prin toate NODURILE o dată. Eulerian: are un ciclu prin toate MUCHIILE o dată.

Gradul extern se citește pe LINIE, gradul intern pe COLOANĂ:

int outDeg = 0;
int inDeg = 0;
for (int j = 0; j < n; j++) {
    if (a[i][j] == 1) {
        outDeg++;
    }
    if (a[j][i] == 1) {
        inDeg++;
    }
}

La graful orientat, a[i][j] = 1 înseamnă DOAR arcul de la i la j; a[j][i] poate fi 0. De aceea fiecare nod are două grade, iar suma gradelor externe este egală cu suma gradelor interne, ambele fiind numărul de arce.

Rădăcina, fiii și frunzele se obțin toate din același tablou t:

// radacina: nodul cu t[i] = 0
for (int i = 1; i <= n; i++) {
    if (t[i] == 0) {
        root = i;
    }
}
// fiii nodului x: pozitiile j cu t[j] = x
for (int j = 1; j <= n; j++) {
    if (t[j] == x) {
        cout << j << " ";
    }
}

Părintele este ascendentul direct, fiii sunt descendenții direcți, iar nodurile cu același părinte sunt frați. Un ascendent este orice nod de pe drumul până la rădăcină, un descendent este orice nod aflat dedesubt, iar un nod fără fii se numește nod terminal sau frunză.

În vectorul de tați, t[i] este PĂRINTELE nodului i. Fiii lui i NU se citesc din t[i], ci se caută printre valori: sunt pozițiile j cu t[j] = i. La fel, o frunză este un nod care nu apare deloc ca valoare în t.

Vectorul de tați: t[i] este părintele lui i, rădăcina are t[i] = 0; ocupă n valori și dă părintele instant. Listele de descendenți: pentru fiecare nod, lista fiilor lui; dau fiii instant. Matricea de adiacență: a[i][j] = 1 dacă i și j sunt legate, simetrică, ocupă $n \cdot n$ valori și răspunde instant la „sunt vecine?”. Aceeași informație, trei feluri de a o ține minte.