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 arbore .
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.
Corolar un graf G contine un arbore partial daca si numai daca G este conex .
Orice arbore cu n >= 2 varfuri contine cel putin 2 varfuri terminale ( de gradul 1 ) .
Orice arbore cu n varfuri are n - 1 muchii .
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.
