Alberi: definizioni di base

Gli alberi vengono definiti come particolari grafi non orientati

Definizione:

• Un albero è un grafo non orientato connesso e acicilco
• Un albero è un grafo non orientato che ammette uno e un solo cammino tra una qualunque coppia di nodi
• Un albero è un grafo non orientato connesso con n nodi e n-1 lati

Si dimostra facilmente che queste definizioni sono equivalenti

Alberi con radice

Un albero con radice è una coppia $\lang r, T \rang$ dove T è un albero e r è un nodo di T

Un albero con radice è un albero in cui si evidenzia un nodo

Il livello (o profondità) di un nodo è la lunghezza del cammino (semplice) che collega la radice dell'albero al nodo

Dati due nodi di un albero x,y diciamo che:

• x è padre di y se x precede y nel cammino semplice che congiunge la radice a y
• y è figlio di x se x è padre di y

Continuando l'analogia "familiare:

• x è fratello di y se x e y hanno lo stesso padre
• x è antenato di y se x compare nel cammino semplice che congiunge la radice a y
• x è discendente di y se y è antenato di x