Arbore

Intuiția

Un arbore este forma cea mai „economică” de a ține toate nodurile legate între ele: fiecare nod e accesibil din oricare altul, dar nu există nicio muchie în plus. Adaugă o singură muchie și apare un ciclu (o buclă, un ocol redundant); șterge una și graful se rupe în bucăți. Arborele stă exact la granița dintre „prea puțin” și „prea mult”.

Vezi cum funcționează

Vizualizarea de mai jos construiește un arbore pe 7 noduri, muchie cu muchie. Urmărește două lucruri: contorul „muchii în arbore” urcă până la exact 6, adică n-1, iar la final apare o muchie suplimentară (între 3 și 4), marcată diferit — ea NU face parte din arbore, pentru că ar închide ciclul 3-1-4.

Ce este

Un arbore este un graf neorientat, conex și fără cicluri.

• Conex = între oricare două noduri există măcar un lanț (poți ajunge de la oricare la oricare).
• Fără cicluri = nu poți pleca dintr-un nod și să te întorci la el pe un traseu care nu repetă muchii (graf aciclic).

Cele două condiții împreună dau proprietăți foarte utile, toate echivalente cu definiția de mai sus pentru un graf pe n noduri:

1. Graful este conex și are exact n-1 muchii.
2. Între oricare două noduri există un UNIC lanț (drum simplu).
3. Graful este fără cicluri și are exact n-1 muchii.
4. Adăugarea oricărei muchii noi creează exact un ciclu; ștergerea oricărei muchii existente deconectează graful.

De ce n-1? Pornești cu un singur nod (zero muchii) și, ca să atașezi fiecare nod nou păstrând conexitatea fără să creezi un ciclu, ai nevoie de exact o muchie. După ce ai legat toate cele n noduri, ai adăugat n-1 muchii.

Cum arată

Iată un arbore pe 5 noduri. Numără muchiile: 4, adică exact n-1. Nodul 0 este legat de 1 și 2; nodul 1 mai are copiii 3 și 4.

Verifică proprietatea lanțului unic: ca să ajungi de la nodul 3 la nodul 2, singurul traseu posibil este 3 → 1 → 0 → 2. Nu există scurtătură și nici o a doua variantă — caracteristic arborilor.

Frunzele

Un nod cu gradul 1 (atins de o singură muchie) se numește frunză. În exemplul de mai sus, frunzele sunt 3, 4 și 2. Orice arbore cu cel puțin două noduri are cel puțin două frunze: capetele celui mai lung lanț din arbore nu pot avea alți vecini — altfel lanțul s-ar prelungi sau s-ar închide un ciclu. Proprietatea e motorul multor demonstrații prin inducție: „smulgi” o frunză și rămâi tot cu un arbore, pe n-1 noduri și n-2 muchii.

Implementare C++

Cum verifici dacă un graf dat este arbore? Aplici fix definiția: trebuie să fie conex ȘI să aibă exact n-1 muchii. Pentru conexitate, pornim un DFS dintr-un nod și numărăm câte noduri reușim să atingem — dacă le atingem pe toate n, graful e conex.

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[1005];    // liste de adiacenta
bool vizitat[1005];

void dfs(int nod) {
    vizitat[nod] = true;
    for (int vecin : adj[nod]) {
        if (!vizitat[vecin]) {
            dfs(vecin);
        }
    }
}

int main() {
    int n = 5, m = 4;
    // muchii ale unui arbore pe 5 noduri (0..4)
    int muchii[4][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}};
    for (int i = 0; i < m; i++) {
        int a = muchii[i][0], b = muchii[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);    // graf neorientat
    }

    // conditia 1: exact n-1 muchii
    bool areNMinus1 = (m == n - 1);

    // conditia 2: conex -> numar nodurile atinse de DFS din nodul 0
    dfs(0);
    int atinse = 0;
    for (int i = 0; i < n; i++) {
        if (vizitat[i]) atinse++;
    }
    bool esteConex = (atinse == n);

    bool esteArbore = areNMinus1 && esteConex;
    cout << (esteArbore ? "DA" : "NU") << "\n";    // DA
    return 0;
}

Reține de ce sunt necesare amândouă verificările: dacă ai n-1 muchii dar graful nu e conex, nu e arbore; dacă e conex dar are mai mult de n-1 muchii, conține un ciclu, deci iar nu e arbore. Numai ambele condiții simultan garantează structura.