Albero (grafo)

In teoria dei grafi, un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino (grafo non orientato, connesso e privo di cicli).

Un albero etichettato con sette vertici e sei cammini.

Si definisce inoltre foresta un grafo non orientato nel quale due vertici qualsiasi sono connessi al più da un cammino (grafo non orientato e privo di cicli). Una foresta risulta costituita da una unione disgiunta di alberi (e questa proprietà giustifica il suo nome); questi alberi costituiscono le sue componenti connesse massimali.

Definizioni

Si dice albero un grafo $G$ connesso, non orientato e senza cicli. Per essere tale, il grafo deve rispettare almeno una delle seguenti richieste:

• Possedere un solo cammino per ogni coppia di vertici.
• Essere aciclico massimale ossia, se gli si aggiunge un altro spigolo per unire due suoi nodi si forma un ciclo.
• Costituire un grafo connesso minimale ossia, se si rimuove un suo spigolo si perde la connessione.

Se $G$ ha un numero finito di $n$ vertici, gli enunciati precedenti sono equivalenti ai due che seguono:

• $G$ è connesso e possiede $n-1$ spigoli.
• $G$ è aciclico (senza cicli) e possiede $n-1$ spigoli.

Si può definire albero un grafo connesso tale che eliminando uno qualsiasi dei suoi spigoli si perde la connessione. Un albero si può quindi apprezzare come grafo connesso economico, in quanto mantiene la connessione impiegando il minimo numero possibile di spigoli.

Si può poi definire albero un grafo aciclico tale che aggiungendo uno spigolo tra due suoi nodi non direttamente connessi si introduce necessariamente un ciclo. Un albero quindi si può apprezzare come grafo aciclico con il maggior numero possibile di connessioni.

Dato un grafo non orientato $G=(V,E)$ si definisce albero di copertura di $G$ un albero $T=(V',E')$ tale che $V'=V$ e $E'$ è un sottoinsieme di $E.$ Se $G$ non è connesso tale albero non esiste.

Si definisce foresta un grafo non orientato aciclico. L'insieme delle foreste include propriamente l'insieme degli alberi, in quanto le foreste connesse sono gli alberi e vi sono foreste non connesse (facilmente individuabili). In una foresta, oltre a eventuali nodi isolati, vi sono sicuramente nodi di valenza 1 che vengono chiamati nodi pendenti: infatti, preso un nodo q qualsiasi, se si individua un cammino che inizia in q cercando di estenderlo progressivamente, ad un certo punto si incontra un nodo di valenza 1, perché in caso contrario si costruirebbe un ciclo, contro l'aciclicità delle foreste. In un albero si trova quindi un nodo pendente. Se si elimina un tale nodo e lo spigolo che incide in esso si ottiene ancora un albero, perché si mantiene la sua connessione e la sua aciclicità.

Procedendo con queste eliminazioni si deve arrivare a un grafo nodo.

Il grafo nodo costituito da un nodo e nessuno spigolo, è un albero (ed anche una foresta).

Viene chiamato grado di un nodo il numero di figli, o di sottoalberi, di un nodo.

Livello

Il livello di un nodo in un albero è pari a 1 più il livello del nodo padre, intendendo che la radice ha livello 0. Per esempio un nodo figlio della radice sarà di livello 1, suo figlio sarà di livello 2.

Altezza

L'altezza di un albero è il massimo fra i livelli di tutti i suoi nodi.

Ogni albero binario con $k$ foglie ha un'altezza maggiore o uguale a $\log _{2}k.$

Dimostrazione

Procedendo per induzione sul numero $k$ di foglie dell'albero considerato si ha che se $k=1$ la proprietà è banalmente verificata ($\log _{2}1=0$ infatti se c'è una sola foglia sarà che l'albero è composto dalla sola radice e quindi l'altezza, per come è definita, sarà 0). Supponiamo la proprietà vera per ogni $j$ tale che $1\leq j\leq k$ e consideriamo un albero binario $T$ con $k$ foglie di altezza minima. Siano $T_{1}$ e $T_{2}$ i due sottoalberi che hanno per radice i figli della radice di $T.$ Si osserva che ciascuno di questi ha meno foglie tra i due e ne possiede almeno $k/2$ (nel caso di numero pari). Allora per ipotesi di induzione l'altezza di quest'ultimo è maggiore o uguale a $\log _{2}{k \over 2}$ quindi anche l'altezza di $T$ è certamente maggiore o uguale a $\log _{2}{k \over 2}$.

Lunghezza del cammino

La lunghezza del cammino interno di un albero binario è data dalla somma dei livelli dei nodi interni, mentre la lunghezza del cammino esterno di un albero binario è data dalla somma dei livelli dei nodi esterni.

Classi di isomorfismo

Gli alberi (o meglio le classi di isomorfismo degli alberi) quindi si possono disporre su diversi livelli caratterizzati dal numero $n$ dei loro nodi. Al livello 1 si trova il grafo nodo, al livello 2 il cammino di 2 nodi, al livello 3 il cammino a tre nodi, al livello 4 il cammino a 4 nodi e la stella a 3 punte e così via. Sul livello $n$ si trovano tutti e soli gli alberi con $n-1$ spigoli che con il processo di riduzione visto sopra si riducono al grafo nodo con $n-1$ passi nei quali diminuisce di uno il numero degli spigoli.

A questo punto è dimostrato che un albero con n nodi possiede $n-1$ spigoli. Viceversa si può dimostrare che un grafo connesso con $n$ nodi e $n-1$ spigoli è aciclico e quindi è un albero. Ma si può dimostrare anche che un grafo aciclico con $n$ nodi e $n-1$ spigoli è connesso e quindi è un albero.

Arricchimenti degli alberi

Si dice albero con radice un albero arricchito da uno dei suoi vertici. Una tale struttura risulta equivalente ad una arborescenza, digrafo tale che possiede un vertice, la radice, dal quale ciascuno degli altri è raggiungibile attraverso uno ed un solo cammino. Essa è anche equivalente ad una controarborescenza, digrafo tale che possiede un vertice, chiamato inghiottitoio, il quale è raggiungibile da ciascuno degli altri attraverso uno ed un solo cammino. In effetti in un albero con radice è possibile orientare tutti gli spigoli in modo che allontanino oppure che avvicinino il nodo privilegiato.

Gli alberi con radice sono strutture di dati usatissime e strategiche in informatica. Spesso risultano utili ulteriori arricchimenti degli alberi con radice: in particolare le strutture per le quali si stabilisce un ordinamento tra i vertici adiacenti ad un dato vertice (v. struttura di dati ad albero). Si dice albero etichettato un albero i cui vertici sono muniti di un'etichetta che li contraddistingue. Spesso le etichette assegnate a un albero con radice ed $n$ vertici sono gli interi da 1 ad $n.$

Esempio

Esempio di albero.

L'esempio di albero mostrato a destra possiede 6 vertici e 6 − 1 = 5 spigoli. L'unico cammino semplice che connette i vertici 2 e 6 è 2-4-5-6.

Proprietà

• Ogni albero è un grafo planare e un grafo bipartito.
• Ogni grafo connesso $G$ ammette un sottoalbero ricoprente, cioè un sottografo che è un albero e che contiene tutti vertici di $G.$
• Dati $n$ vertici etichettati (e distinguibili), ci sono $n^{n-2}$ modi diversi per collegarli per trasformarli in un albero. Questo risultato è chiamato formula di Cayley.
• Il numero degli alberi con $n$ vertici di grado $d_{1},d_{2},\ldots ,d_{n}$ è

${n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.$

Questo è chiamato coefficiente multinomiale.

• Non è nota alcuna espressione chiusa per il numero $t(n)$ degli alberi astratti con $n$ vertici, ossia il numero delle classi di isomorfismo di alberi. È però noto il comportamento asintotico di $t(n)$: esistono due numeri $\alpha \approx 3$ e $\beta \approx 0,5$ tali che

$\lim _{n\to \infty }{\frac {t(n)}{\beta \alpha ^{n}n^{-5/2}}}=1.$

• Ogni albero con un numero maggiore o uguale a 2 nodi possiede almeno 2 foglie.
• Ogni albero con $n$ nodi possiede $n-1$ lati (per il teorema di Cayley).
• Esiste un unico cammino tra qualsiasi coppia di nodi.
• Se consideriamo un albero di supporto ed il suo grafo di appartenenza, aggiungendo all'albero un lato che non gli appartiene ma che appartiene al grafo, si crea un unico ciclo.

Proprietà alberi binari

Concentrandosi sugli alberi binari esistono numerose proprietà matematiche che sono ricorrenti nell'analisi degli algoritmi.

Un albero binario con $N$ nodi interni ha $N+1$ nodi esterni.

Questa proprietà può essere dimostrata per induzione. Un albero binario senza nodi interni ha un nodo esterno, per cui la proprietà è valida per $N=0.$ Per $N>0,$ un qualsiasi albero binario con $N$ nodi interni ha 1 nodo interno nel sottoalbero destro ed $N-1-k$ nel sottoalbero sinistro essendo la radice un nodo interno. Per induzione, il sottoalbero sinistro ha $k+1$ nodi esterni mentre il destro ne ha $N-k$ per un totale di $N+1.$

Un albero binario con $N$ nodi interni ha $2N$ archi: $N-1$ archi interni e $N+1$ archi esterni.

In ogni albero con radice, ogni nodo ha un unico padre, e ogni arco connette un nodo al padre del nodo. Quindi ci sono $N-1$ archi che connettono nodi interni. Similmente ciascuno degli $N+1$ nodi esterni ha un arco che punta verso l'unico padre. Le prestazioni di molti algoritmi dipendono non solo dal numero di nodi dell'albero associato ma anche da varie proprietà strutturali di questo.

Tipi di alberi

Lo schema del classico grafo ad albero usato per descrivere la gerarchia tra un fiume (ordine 1) e i suoi affluenti e sub-affluenti.

Albero con radice

Un albero con radice è una coppia $(T,r)$ dove $T$ è un albero e $r$ un suo vertice che viene detto radice. Un albero con radice è quindi un albero in cui viene evidenziato un vertice (la radice); esso viene anche detto albero radicato. Ora, dato un vertice $x$ in un albero con radice $r,$ c'è un unico cammino semplice $(r,V_{2},V_{3},\ldots ,V_{m},x)$ da $r$ a $x$ (se $r\neq x$); il vertice $V_{m}$ che precede il vertice $x$ è detto padre di $x.$

Albero ordinato

Un albero ordinato (detto anche piano) è un albero radicato in cui i figli di ogni vertice sono totalmente ordinati.

Un figlio della radice coi suoi discendenti forma a sua volta un albero ordinato. Questo fatto permette di dare la seguente definizione induttiva di albero ordinato: $k$ (definiti su insiemi di vertici disgiunti) e $r$ è un nodo diverso dai nodi di $T_{1},T_{2},\ldots ,T_{m},$ allora la sequenza $(r,T_{1},T_{2},\ldots ,T_{m})$ è un albero ordinato.

Albero binario

Un albero binario è un albero radicato in cui ogni nodo interno ha al più due figli; ogni figlio è distinto come figlio sinistro oppure figlio destro. I seguenti due alberi sono coincidenti come alberi ordinati, ma distinti come alberi binari:

Dato un vertice $x$ di un albero $T$ binario, il sottoalbero che ha come radice il figlio sinistro di $x$ se esiste, sarà detto sottoalbero sinistro di $x.$

Albero binario completo di altezza h

Un albero binario completo è un albero binario in cui ogni nodo interno è pieno (ha entrambi i figli) e tutte le foglie sono allo stesso livello, ossia hanno la stessa distanza dalla radice. Un albero viene chiamato albero quasi completo se, rispetto ad un albero completo, mancano alcune foglie (ossia alcuni nodi sul penultimo livello non sono pieni). Questo tipo di albero è usato come una struttura dati specializzata chiamata heap.

Il numero di vertici di un albero binario completo di altezza $h$ risulta essere:

$n=\sum _{j=0}^{h}2^{j}=2^{h+1}-1$

e quindi

$h\to \log {n},\quad$ per $n\to \infty .$

Da questo possiamo dedurre che alberi completi contengono un gran numero di nodi con una bassa altezza.

Arborescenze

Se si prende un albero e si evidenzia un suo nodo, cioè se si arricchisce l'informazione che individua un albero con la segnalazione di un suo nodo, si ottiene una struttura leggermente diversa ma sostanzialmente più ricca. Questa conviene chiamarla arborescenza e considerarla un digrafo, in quanto gli spigoli dell'albero originale si possono orientare in modo che si abbia un cammino orientato che porta dal nodo privilegiato a un qualsiasi altro nodo.

Il genere di struttura così ottenuto viene spesso chiamato specie degli alberi con radice (rooted trees). Questo termine è molto usato in informatica.

A questo proposito occorre osservare che nelle applicazioni servono di più le arborescenze degli alberi, anzi servono arborescenze arricchite da altre informazioni: questo accade ad es. con gli alberi sintattici trattati dai compilatori o nella linguistica e con gli organigrammi ad albero, gerarchici. Accade allora che in certe aree applicative si usi il termine albero per indicare un'arborescenza munita di certe altre informazioni. Quando si fa della matematica è invece opportuno attenersi a definizioni precise, possibilmente standard.

Nell'ambito di determinati settori si può invece accettare l'uso improprio (per la matematica) del termine albero, purché sia considerato un termine gergale, di uso circoscritto e giustificabile mediante convenzioni magari non esplicite ma esplicitabili e purché vi sia coscienza delle possibilità di fraintendimenti insite nell'uso affrettato dei termini.

Voci correlate

• Albero (informatica)
• Albero binario
• Albero ricoprente

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su albero