Arborii

Noțiuni preliminare

Graful neorientat este perechea de mulțimi G = (V, U), în care V este o mulțime finită și nevidă de elemente numite vârfuri, iar U este o mulțime de perechi neordonate de vârfuri distincte, numite muchii. Perechea fiind neordonată, muchia [x, y] și muchia [y, x] sunt una și aceeași; de aici și numele: legătura nu are sens.

Lanțul este o succesiune de vârfuri v₁, v₂, …, v_k cu proprietatea că oricare două vârfuri consecutive din succesiune sunt legate printr-o muchie a grafului. Lungimea lanțului este numărul muchiilor parcurse, adică k−1. Un lanț se numește elementar dacă toate vârfurile din el sunt distincte.

Ciclul este un lanț în care primul și ultimul vârf coincid, toate muchiile parcurse sunt distincte, iar lungimea este cel puțin 3. Ciclul se numește elementar dacă, în afară de primul și ultimul, toate vârfurile sunt distincte.

Cinci definiții echivalente ale unui arbore

Fie G un graf neorientat cu n vârfuri și m muchii. Fiecare dintre următoarele afirmații poate fi luată ca definiție a arborelui, iar celelalte se demonstrează pornind de la ea.

1. G este conex și fără cicluri. Aceasta este definiția obișnuită: între oricare două vârfuri există un lanț, iar graful nu conține niciun ciclu.

2. G este conex și are exact n−1 muchii. Conexitatea cere cel puțin n−1 muchii; dacă are exact atâtea, nu-i mai rămâne niciuna care să închidă un ciclu.

3. G este fără cicluri și are exact n−1 muchii. Un graf aciclic cu n vârfuri are cel mult n−1 muchii, iar egalitatea se atinge numai când este și conex.

4. Între oricare două vârfuri ale lui G există un lanț elementar unic. Existența lanțului înseamnă conexitate, iar unicitatea lui exclude ciclurile: două lanțuri distincte între aceleași două vârfuri ar forma împreună un ciclu.

5. G este conex, dar prin eliminarea oricărei muchii devine neconex. Arborele este, în acest sens, minimal conex: nu are nicio muchie de prisos.

Problema propusă

Enunț. Se citesc de la tastatură două numere naturale n și m (2 ≤ n ≤ 100), reprezentând numărul de vârfuri și numărul de muchii ale unui graf neorientat, apoi m perechi de numere naturale din intervalul [1, n], reprezentând extremitățile muchiilor. Se cere să se afișeze pe ecran mesajul DA, dacă graful citit este arbore, sau mesajul NU în caz contrar.

Exemplu: pentru n = 5, m = 4 și muchiile [1,2], [1,3], [3,4], [3,5] se afișează DA; pentru n = 5, m = 4 și muchiile [1,2], [2,3], [1,3], [4,5] se afișează NU.

Descrierea soluției în limbaj natural. Se folosește a doua dintre definițiile de mai sus: graful este arbore dacă și numai dacă este conex și are exact n−1 muchii. Verificarea se face în doi pași, iar amândoi sunt necesari — niciunul singur nu este de ajuns.

Prima condiție se verifică imediat, comparând m cu n−1. Dacă numărul muchiilor este diferit, graful nu poate fi arbore și răspunsul este NU, fără să mai fie nevoie de alte verificări.

A doua condiție cere să se stabilească dacă graful este conex. Se pornește de la vârful 1 și se parcurge graful în adâncime, marcând fiecare vârf la care se ajunge. La sfârșitul parcurgerii se verifică dacă toate cele n vârfuri au fost marcate: dacă da, între vârful 1 și oricare altul există un lanț, deci graful este conex; dacă a rămas cel puțin un vârf nemarcat, graful are mai multe componente conexe.

Dacă amândouă condițiile sunt îndeplinite, graful este arbore.

Al doilea set de date din exemplu arată de ce prima condiție nu este de ajuns: graful are 5 vârfuri și 4 muchii, deci exact n−1, dar vârfurile 1, 2 și 3 formează un ciclu, iar 4 și 5 rămân despărțite de restul. Numărul muchiilor iese la socoteală tocmai pentru că o muchie „de prisos”, cea care închide ciclul, compensează muchia care lipsește pentru a lega a doua componentă.

Implementarea soluției.

#include <iostream>
using namespace std;

int a[101][101];     // matricea de adiacenta
bool vizitat[101];
int n, m;

/* Parcurgere in adancime, pornind din varful x. */
void dfs(int x) {
    vizitat[x] = true;
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && !vizitat[y])
            dfs(y);
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;    // graf neorientat: matricea este simetrica
    }

    /* Prima conditie: numarul de muchii. */
    if (m != n - 1) {
        cout << "NU";
        return 0;
    }

    /* A doua conditie: conexitatea. */
    dfs(1);
    for (int i = 1; i <= n; i++)
        if (!vizitat[i]) {
            cout << "NU";
            return 0;
        }

    cout << "DA";

    return 0;
}

Verificarea pe exemplele din enunț.