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 :

1. G este un arbore . 38571bbf77kmv3e

2. G este un graf conex minimal , adica G este conex si daca ii suprimam o muchie oarecare [x ,y ]. Graful obtinut devine neconex.

3. 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.

Proprietati ale arborilor

Corolar un graf G contine un arbore partial daca si numai daca G este conex . bm571b8377kmmv

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.