TreeEdit

Un albero è un grafo G non orientato che soddisfa una delle seguenti condizioni equivalenti:

• G è connesso e aciclico (non contiene cicli).
• G è aciclico e si forma un ciclo semplice se viene aggiunto un bordo a G.
• G è collegato, ma si disconnetterebbe se un singolo bordo viene rimosso da G.
• G è collegato e il grafico completo a 3 vertici K3 non è minore di G.
• Qualsiasi due vertici in G possono essere collegati da un unico

Se G ha finitamente molti vertici, diciamo n di essi, allora le istruzioni precedenti sono anche equivalenti a una qualsiasi delle seguenti condizioni:

• G è connesso e ha n − 1 bordi.
• G è connesso e ogni sottografo di G include almeno un vertice con zero o uno spigolo incidente. (Cioè, G è connesso e 1-degenerato.)
• G non ha cicli semplici e ha n-1 bordi.

Come altrove nella teoria dei grafi, il grafico ordine-zero (grafico senza vertici) non è generalmente considerato un albero: mentre è collegato vacuamente come un grafico (due vertici possono essere collegati da un percorso), non è collegato a 0 (o anche (-1)-connesso) nella topologia algebrica, a differenza degli alberi non vuoti, e viola la relazione “un altro vertice rispetto ai bordi”. Può, tuttavia, essere considerato come una foresta composta da zero alberi.

Un vertice interno (o vertice interno o vertice di ramo) è un vertice di grado almeno 2. Allo stesso modo, un vertice esterno (o vertice esterno, vertice terminale o foglia) è un vertice di grado 1.

Un albero irriducibile (o albero ridotto in serie) è un albero in cui non esiste un vertice di grado 2 (enumerato nella sequenza A000014 nell’OEIS).

ForestEdit

Una foresta è un grafico non orientato in cui due vertici sono collegati al massimo da un percorso. Equivalentemente, una foresta è un grafico aciclico non orientato, tutti i cui componenti collegati sono alberi; in altre parole, il grafico consiste in un’unione disgiunta di alberi. Come casi speciali, il grafico ordine-zero (una foresta composta da zero alberi), un singolo albero e un grafico senza spigoli, sono esempi di foreste.Poiché per ogni albero V-E = 1, possiamo facilmente contare il numero di alberi che si trovano all’interno di una foresta sottraendo la differenza tra i vertici totali e i bordi totali. TV-TE = numero di alberi in una foresta.

PolytreeEdit

Un polytree (o albero diretto o albero orientato o rete collegata singolarmente) è un grafico aciclico diretto (DAG) il cui sottostante grafico non orientato è un albero. In altre parole, se sostituiamo i suoi bordi diretti con bordi non orientati, otteniamo un grafico non orientato che è sia connesso che aciclico.

Alcuni autori limitano la frase “albero diretto” al caso in cui i bordi sono tutti diretti verso un particolare vertice, o tutti diretti lontano da un particolare vertice (vedi arborescenza).

PolyforestEdit

Un polyforest (o foresta diretta o foresta orientata) è un grafico aciclico diretto il cui sottostante grafico non orientato è una foresta. In altre parole, se sostituiamo i suoi bordi diretti con bordi non orientati, otteniamo un grafico non orientato che è aciclico.

Alcuni autori limitano la frase “foresta diretta” al caso in cui i bordi di ogni componente connesso sono tutti diretti verso un particolare vertice, o tutti diretti lontano da un particolare vertice (vedi ramificazione).

Albero radicato

Un albero radicato è un albero in cui un vertice è stato designato radice. Ai bordi di un albero radicato può essere assegnato un orientamento naturale, lontano o verso la radice, nel qual caso la struttura diventa un albero radicato diretto. Quando un albero radicato diretto ha un orientamento lontano dalla radice, è chiamato arborescenza o fuori-albero; quando ha un orientamento verso la radice, è chiamato anti-arborescenza o in-albero. L’albero-ordine è un ordinamento parziale sui vertici di un albero con u < v se e solo se l’unico percorso dalla radice a v passa attraverso u. Un albero radicato T che è un sottografi di alcuni grafo G è un normale albero se le estremità di ogni T-percorso in G sono paragonabili in questo albero di ordine (Diestel 2005, p. 15). Gli alberi radicati, spesso con struttura aggiuntiva come l’ordinamento dei vicini a ciascun vertice, sono una struttura dati chiave nell’informatica; vedi struttura dati ad albero.

In un contesto in cui gli alberi dovrebbero avere una radice, un albero senza alcuna radice designata è chiamato albero libero.

Un albero etichettato è un albero in cui ad ogni vertice viene assegnata un’etichetta univoca. I vertici di un albero etichettato su n vertici sono in genere date le etichette 1, 2,…, n. Un albero ricorsivo è un albero radicato etichettato in cui le etichette dei vertici rispettano l’ordine degli alberi (cioè, se u < v per due vertici u e v, allora l’etichetta di u è più piccola dell’etichetta di v).

In un albero radicato, il genitore di un vertice v è il vertice collegato a v sul percorso della radice; ogni vertice ha un genitore univoco tranne la radice che non ha genitore. Un figlio di un vertice v è un vertice di cui v è il genitore. Un ascendente di un vertice v è qualsiasi vertice che è il genitore di v o è (ricorsivamente) l’ascendente del genitore di v. Un discendente di un vertice v è qualsiasi vertice che è figlio di v o è (ricorsivamente) il discendente di uno qualsiasi dei figli di v. Un fratello di un vertice v è qualsiasi altro vertice sull’albero che ha lo stesso genitore di v. Una foglia è un vertice senza figli. Un vertice interno è un vertice che non è una foglia.

L’altezza di un vertice in un albero radicato è la lunghezza del percorso verso il basso più lungo di una foglia da quel vertice. L’altezza dell’albero è l’altezza della radice. La profondità di un vertice è la lunghezza del percorso alla sua radice (percorso radice). Questo è comunemente necessario nella manipolazione dei vari alberi di auto-bilanciamento, alberi AVL in particolare. La radice ha profondità zero, le foglie hanno altezza zero e un albero con un solo vertice (quindi sia una radice che una foglia) ha profondità e altezza zero. Convenzionalmente, un albero vuoto (un albero senza vertici, se consentito) ha profondità e altezza -1.

Un albero k-ary è un albero radicato in cui ogni vertice ha al massimo k bambini. gli alberi 2-ary sono spesso chiamati alberi binari, mentre gli alberi 3-ary sono talvolta chiamati alberi ternari.

Albero ordinatoedit

Un albero ordinato (o platano) è un albero radicato in cui viene specificato un ordine per i figli di ciascun vertice. Questo è chiamato “platano” perché un ordinamento dei figli equivale a un incorporamento dell’albero nel piano, con la radice in alto e i figli di ciascun vertice inferiori a quel vertice. Dato un incorporamento di un albero radicato nel piano, se si fissa una direzione dei bambini, diciamo da sinistra a destra, allora un incorporamento dà un ordine dei bambini. Al contrario, dato un albero ordinato e disegnando convenzionalmente la radice in alto, i vertici figlio in un albero ordinato possono essere disegnati da sinistra a destra, ottenendo un embedding planare essenzialmente unico.