Arbori

Grafurile fără cicluri: proprietățile care se cer la teorie, arborele cu rădăcină și vectorul de tați.

Definiția

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

Contează amândouă condițiile. Un graf fără cicluri, dar neconex, se numește pădure, adică o mulțime de arbori.

Proprietățile

Toate se cer la Subiectul I și toate decurg una din alta.

Un arbore cu n vârfuri are exact n - 1 muchii.

Între oricare două vârfuri există un lanț unic. Dacă ar exista două lanțuri diferite, împreună ar forma un ciclu.

Dacă adaugi o muchie, apare exact un ciclu. Muchia nouă închide lanțul care exista deja între capetele ei.

Dacă ștergi o muchie, graful se rupe în două componente. Nu există alt drum de rezervă.

De aici vine o caracterizare utilă. Un arbore este un graf conex minimal: are cât mai puține muchii cu putință fără să se rupă. În același timp, este un graf aciclic maximal: nu mai poți adăuga nicio muchie fără să creezi un ciclu.

În practică, poți verifica așa: dacă un graf cu n vârfuri are n - 1 muchii și este conex, este arbore. Oricare două dintre cele trei condiții (conex, aciclic, n-1 muchii) o implică pe a treia.

Vârfuri terminale

Un vârf de grad 1 se numește terminal (sau frunză, când arborele are rădăcină).

Orice arbore cu cel puțin două vârfuri are cel puțin două vârfuri terminale. Motivul e simplu: capetele celui mai lung lanț din arbore nu pot avea alți vecini, altfel lanțul ar putea fi prelungit.

Arbore cu rădăcină

Dacă alegi un vârf și îl numești rădăcină, arborele capătă niveluri și un sens: de la rădăcină în jos.

Apar câteva noțiuni noi:

• Tatăl unui vârf: vecinul lui aflat cu un nivel mai sus. Rădăcina nu are tată.
• Fiii unui vârf: vecinii aflați cu un nivel mai jos.
• Frunză: vârf fără fii.
• Nivelul unui vârf: distanța până la rădăcină. Rădăcina are nivelul 0 (sau 1, după convenția din enunț, pe care trebuie s-o citești cu atenție).
• Înălțimea arborelui: nivelul maxim.
• Descendenții unui vârf: toate vârfurile din subarborele lui.

Dacă schimbi rădăcina, același arbore are alți tați și alte niveluri. Rădăcina o alegi tu, nu e o proprietate a arborelui.

Vectorul de tați

Este cea mai compactă reprezentare a unui arbore cu rădăcină. t[i] este tatăl vârfului i, iar rădăcina are t[rad] = 0.

i:     1  2  3  4  5  6
t[i]:  0  1  1  2  2  3

Rădăcina este 1, iar vârfurile 2 și 3 sunt fiii ei. 4 și 5 sunt fiii lui 2, iar 6 este fiul lui 3.

Un singur vector reține toată structura. Din el afli direct:

// rădăcina
for (int i = 1; i <= n; i++)
    if (t[i] == 0) rad = i;

// fiii lui x
for (int i = 1; i <= n; i++)
    if (t[i] == x) cout << i << " ";

// frunzele: vârfurile care nu sunt tatăl nimănui
bool areFii[101] = {false};
for (int i = 1; i <= n; i++)
    if (t[i] != 0) areFii[t[i]] = true;
for (int i = 1; i <= n; i++)
    if (!areFii[i]) cout << i << " ";

Drumul de la un vârf la rădăcină îl obții urcând din tată în tată:

int x = start;
while (x != 0) {
    cout << x << " ";
    x = t[x];
}

Bucla se termină sigur, pentru că într-un arbore nu există cicluri. Urcând, ajungi mereu la rădăcină.

Nivelul unui vârf este numărul de pași până la rădăcină:

int nivel(int x) {
    int k = 0;
    while (t[x] != 0) {
        x = t[x];
        k++;
    }
    return k;
}

Strămoșul comun

Pentru două vârfuri date, care este cel mai apropiat vârf aflat pe drumul spre rădăcină al amândurora?

Metoda simplă, suficientă la bac: marchezi tot drumul primului vârf spre rădăcină, apoi urci din al doilea până dai peste un vârf marcat.

bool pe_drum[101] = {false};
int x = a;
while (x != 0) { pe_drum[x] = true; x = t[x]; }

int y = b;
while (!pe_drum[y]) y = t[y];
cout << y;

A doua buclă se termină sigur. Rădăcina este marcată, deci în cel mai rău caz se oprește acolo.

Câteva calcule de teorie

> Câte muchii are o pădure cu n vârfuri și k arbori?

Fiecare arbore cu nᵢ vârfuri are nᵢ - 1 muchii. Dacă aduni, obții n - k.

> Un arbore are 3 vârfuri de grad 3, 2 de grad 2 și restul terminale. Câte vârfuri are?

Fie f numărul de frunze. Suma gradelor este 3·3 + 2·2 + f = 13 + f, iar numărul de vârfuri este 5 + f. Într-un arbore, suma gradelor este 2(n-1), deci 13 + f = 2(5 + f - 1) = 8 + 2f, de unde f = 5 și n = 10.

La acest gen de item scrii suma gradelor în două feluri și rezolvi ecuația.

De reținut

• Arbore = conex + fără cicluri. Are exact n - 1 muchii.
• Între oricare două vârfuri există un lanț unic.
• Oricare două din „conex", „aciclic", „n-1 muchii" o dau pe a treia.
• Rădăcina o alegi tu. De ea depind tații și nivelurile.
• Vectorul de tați reține tot arborele. Urcarea spre rădăcină se termină întotdeauna.
• O pădure cu n vârfuri și k arbori are n - k muchii.