Grafuri neorientate: terminologie

Ce este un graf neorientat

Un graf neorientat $G = (V, E)$ are o mulțime de noduri (vârfuri) $V$ și o mulțime de muchii $E$. O muchie leagă două noduri și nu are sens: $[x, y]$ și $[y, x]$ sunt aceeași muchie.

Terminologia cerută de programă

• Nod (vârf): element al mulțimii $V$.
• Muchie: pereche neordonată de noduri distincte.
• Adiacență: două noduri sunt adiacente dacă între ele există muchie.
• Incidență: o muchie este incidentă cu nodurile pe care le unește.
• Grad ($d(x)$): numărul de muchii incidente cu nodul $x$. Un nod cu gradul 0 se numește izolat, cu gradul 1 terminal.
• Lanț: succesiune de noduri în care oricare două consecutive sunt adiacente.
• Lanț elementar: lanț în care niciun nod nu se repetă.
• Ciclu: lanț în care primul nod coincide cu ultimul, cu cel puțin 3 muchii distincte.
• Ciclu elementar: ciclu în care nu se repetă niciun nod, în afară de primul și ultimul.
• Lungime: numărul de muchii din lanț sau ciclu, nu numărul de noduri.
• Subgraf: se obține eliminând noduri și toate muchiile incidente cu ele.
• Graf parțial: se obține eliminând doar muchii; nodurile rămân toate.

Teorema gradelor

$\sum_{x \in V} d(x) = 2 \cdot m$

Suma gradelor tuturor nodurilor este dublul numărului de muchii, pentru că fiecare muchie contribuie cu 1 la gradul fiecăruia dintre cele două capete.

Consecință: suma gradelor e întotdeauna pară, iar numărul nodurilor de grad impar e par.

Greșeli frecvente

1. Se numără lungimea în noduri. Se numără în muchii: un lanț cu 4 noduri are lungimea 3.
2. Se confundă subgraful cu graful parțial.
3. Se uită că într-un graf neorientat muchia nu are sens, deci matricea de adiacență e simetrică.

#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] = a[y][x] = 1;
    }

    int suma = 0, izolate = 0, terminale = 0;
    for (int i = 1; i <= n; i++) {
        int g = 0;
        for (int j = 1; j <= n; j++) g += a[i][j];
        suma += g;
        if (g == 0) izolate++;
        if (g == 1) terminale++;
    }

    cout << "suma gradelor=" << suma << " muchii=" << suma / 2;
    cout << " izolate=" << izolate << " terminale=" << terminale;
    return 0;
}