Definiție
Definiția simplă: arborele este un graf neorientat conex care nu conține cicluri.
Arborele este un graf neorientat conex în care unul din noduri este desemnat rădăcină. Nodurile pot fi așezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.
Nu există o regulă pentru cum se alege rădăcina, îl alegem noi sau ni se dă în problemă.
- Într-un arbore cu noduri avem muchii.
- Un arbore este un graf conex și minimal cu această proprietate; dacă s-ar mai elimina o muchie, graful nu ar mai fi conex.
- Un arbore este un graf aciclic și maximal cu această proprietate; dacă s-ar mai adăuga o muchie, s-ar obține un ciclu.
Rădăcina
Rădăcina este un nod special care generează așezarea unui arbore pe niveluri. Această operație se efectuează în funcție de lungimea lanțurilor prin care celelalte noduri sunt legate de rădăcină.
Niveluri
Nivelul unui nod este dat de lungimea lanțului până la rădăcină +1
Descendent
Într-un arbore nodul este descendent al nodului dacă este situat pe un nivel mai mare decât nivelul lui și există un lanț care le unește și nu trece prin rădăcină.
Descendent direct (fiu)
Într-un arbore nodul este descendent direct (fiu) al nodului dacă este situat pe nivelul imediat următor lui și există muchie între și .
Ascendent
Într-un arbore cu rădăcină nodul este ascendentul nodului dacă este situat pe un nivel mai mic decât al lui și există un lanț care le unește și nu trece prin rădăcină.
Ascendent direct (părinte)
Într-un arbore nodul este ascendent direct (părinte) al nodului dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) lui și există muchie între și . Practic daca este descendentul (direct) al lui , este ascendentul (direct) al lui
Frați
Într-un arbore nodul este fratele nodului dacă au același părinte (ascendent direct).
Frunză
Într-un arbore cu rădăcină nodul este frunză dacă nu are nici un descendent (implicit nu are nici un fiu sau descendent direct)