Arbori

Un graf conex si fara cicluri se nmeste arbore. In urmatorul desen vom avea un arbore cu 10 varfuri. Se observa ca oricare ar fimuchia arborelui pe care am suprima o se obtine un graf neconex care are doua componente conex. De asemenea oricare ar fi perechea de varfuri neadiacente ale unui arbore pe care le am unii printr-o muchie se creaza un ciclu unic De exemplu, daca adaugam muchia [3, 4] apare ciclul [2, 3, 4, 2], daca adaugam muchia [5, 7] apare ciclul [5, 1, 10, 7, 5] etc. Aceste proprietati au loc pentru orice arbore, asa cum rezulta din teorema: urmatoarele afirmatii sunt echivalente pentru un graf G: G este un graf conex minimal, adica G este conex si daca ii suprimam o muchie oarecare [x, y]. Graful obtinut devine neconex.

G este un graf fara cicluri maximal, adica G nu contine cicluri si daca x si y sunt doua varfuri neadiacente ale lui G atunci graful obtinut din G prin adaugarea muchiei [x, y] contine un ciclul.

Arbori binari si aplicatii Un arbore binar se defineste in modul urmator: un arbore care are un varf numit radacina, al carui grad este 0, unu sau doi. Daca gradul radacinii este 0, arborele binar este format numai din radacina. In caz contrar, radacina se leaga printr o muchie sau prin doua muchii de unul sau de doua alte noi varfuri care se deseneaza sub radacina care se numesc fiii varfului radacina. Modul in care varfurile fiu se deseneaza sub radacina, la stanga sau la dreapta, are importanta. Aeste noduri fiu au fiecare 0, 1, 2 noduri fiu, la stanga sau la dreapta s. a. m. d. Vom spune ca radacina arborelui are nivelul 0, fii radacinii nivelului 1, fii acestora nivelul 2, descendentii de ordin k ai radacinii nivelul k si ii vom desena la aceeasi inaltime fata de marginea de jos a unei pagini.

...