Noțiunea de arbore

Un arbore este un graf neorientat conex și fără cicluri. Lanțul 1–2–3 este arbore: orice pereche de vârfuri poate fi legată și nu există ciclu. Dacă adăugăm muchia 1–3, apare un ciclu, deci noul graf nu mai este arbore. Lecțiile „Arbore cu rădăcină”, „Reprezentarea arborelui”, „Parcurgerea arborelui”, „Arbore binar” și „Arbore binar de căutare” dezvoltă organizări și operații diferite.

Un arbore cu $n$ vârfuri are $n-1$ muchii și un singur lanț simplu între oricare două vârfuri. Eliminarea oricărei muchii îl deconectează; adăugarea unei muchii între două vârfuri deja existente creează un ciclu. Un vârf de grad 1 se numește frunză, iar un arbore cu $n\ge 2$ vârfuri are cel puțin două frunze. Suma gradelor este $2(n-1)$. Orice arbore cu $n\ge 2$ vârfuri se obține dintr-unul cu $n-1$ vârfuri adăugând o frunză, adică un vârf nou legat printr-o singură muchie de un vârf existent; de aceea numărul muchiilor crește cu 1 la fiecare vârf nou.

Calculează acum pentru $V=\{1,2,3,4\}$ și $E=\{[1,2],[2,3],[2,4]\}$. Sunt patru vârfuri și trei muchii. Pornind din 1 ajungi la 2, apoi la 3 și 4, deci graful este conex. Nu există ciclu: vârfurile 1, 3 și 4 sunt frunze, fiecare cu gradul 1. Lanțul unic de la 3 la 4 este 3–2–4. Dacă elimini $[2,4]$, vârful 4 se izolează; dacă adaugi $[1,3]$, apare ciclul 1–2–3–1. Acest calcul arată două caracterizări echivalente ale arborelui: conex cu $n-1$ muchii și aciclic cu $n-1$ muchii.

Exemplul 1 — testul de arbore. Programul citește $n$ și $m$, apoi muchiile, și afirmă că graful este arbore dacă are $m=n-1$ muchii și este conex:

#include <iostream>
using namespace std;
int a[11][11], viz[11], n, m;
void df(int u) {
    viz[u] = 1;
    for (int v = 1; v <= n; ++v)
        if (a[u][v] && !viz[v]) df(v);
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    df(1);
    bool conex = true;
    for (int i = 1; i <= n; ++i)
        if (!viz[i]) conex = false;
    cout << (m == n - 1 && conex ? "arbore" : "nu");
}

Pentru 4 3 cu muchiile $[1,2]$, $[2,3]$, $[2,4]$ se afișează arbore. Pentru 4 3 cu muchiile $[1,2]$, $[2,3]$, $[3,1]$ se afișează nu: numărul muchiilor este tot $n-1=3$, dar vârful 4 rămâne izolat, iar muchiile $[1,2]$, $[2,3]$, $[3,1]$ formează un ciclu. Parcurgerea cu matrice cere $O(n^2)$ operații; cu liste de adiacență, o parcurgere DFS sau BFS verifică existența drumului către fiecare vârf în $O(n+m)$.

Exemplul 2 — câți arbori au patru vârfuri etichetate. Graful complet $K_4$ are 6 muchii, iar un arbore folosește 3 dintre ele, deci există $C_6^3=20$ submulțimi de câte trei muchii. Toate au exact $n-1=3$ muchii, dar nu toate sunt arbori: o submulțime este arbore dacă este conexă. Cele patru submulțimi care formează un triunghi (de exemplu $[1,2]$, $[2,3]$, $[3,1]$) lasă un vârf izolat, deci rămân $20-4=16$ arbori. Numărul lor, $4^{4-2}=16$, confirmă formula $n^{n-2}$ pentru arbori etichetați. Exemplul arată cât de important este să verifici și conexitatea.

Exemplul 3 — frunzele unui arbore cu grade date. Un arbore are 8 vârfuri: două de grad 3, iar celelalte de grad 1 sau 2. Suma gradelor este $2(8-1)=14$. Notăm cu $k$ numărul frunzelor și cu $r$ numărul vârfurilor de grad 2. Numărul de vârfuri dă $2+k+r=8$, iar suma gradelor dă $6+k+2r=14$. Scăzând prima relație din a doua obținem $4+r=6$, deci $r=2$ și $k=4$. Un arbore cu aceste grade: vârfurile $u$ și $v$ sunt adiacente; $u$ are frunza $a$ și vecinul $w$, iar $w$ are frunza $b$; $v$ are frunza $c$ și vecinul $z$, iar $z$ are frunza $d$.

Testul $m=n-1$ este necesar, dar singur nu ajunge: un graf cu trei vârfuri într-o componentă ciclică și un vârf izolat poate avea tot $n-1$ muchii. Verifică și conexitatea sau absența ciclurilor. Pentru un graf neorientat simplu cu $n\ge 1$, oricare două dintre condițiile „conex”, „aciclic”, „are $n-1$ muchii” implică a treia. Un graf aciclic cu $k$ componente conexe (o pădure) are $n-k$ muchii. Dacă un graf cu $n$ vârfuri are un ciclu și exact $n-1$ muchii, el nu poate fi conex, pentru că un graf conex cu $n-1$ muchii este arbore. Cele două frunze ale unui lanț cu $n$ vârfuri sunt numărul minim; un arbore în care un vârf este adiacent cu toate celelalte (o stea) are $n-1$ frunze.

Exemplu în formatul examenului. Un graf neorientat are 6 vârfuri, 5 muchii și cel puțin un ciclu. Care afirmație este adevărată?

• a) Graful este arbore.
• b) Graful nu este conex.
• c) Graful are exact două componente conexe.
• d) Graful are un vârf izolat.

Răspunsul corect este b). Un graf conex cu 6 vârfuri și 5 muchii este arbore, deci nu are cicluri; graful dat are un ciclu, așadar nu este conex. Varianta a) contrazice existența ciclului. Varianta c) nu rezultă obligatoriu: patru vârfuri unite prin cinci muchii ($K_4$ fără o muchie) și vârfurile 5 și 6 izolate dau 6 vârfuri, 5 muchii, cicluri și trei componente. Varianta d) nu rezultă nici ea: triunghiul $[1,2]$, $[2,3]$, $[3,1]$ plus muchiile $[4,5]$ și $[5,6]$ are 6 vârfuri, 5 muchii, un ciclu și niciun vârf izolat.

Greșeli frecvente

• Greșit: orice graf cu $n-1$ muchii este arbore.
  Corect: trebuie verificată și conexitatea.
• Greșit: un arbore poate avea ciclu.
  Corect: este aciclic.
• Greșit: între două vârfuri ale arborelui sunt mai multe lanțuri simple.
  Corect: există exact unul.

Înainte și după