[go: up one dir, main page]
More Web Proxy on the site http://driver.im/Vai al contenuto

Albero (grafo)

Da Wikipedia, l'enciclopedia libera.
Un albero etichettato con sette vertici e sei cammini.

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

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.

Si dice albero un grafo 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 ha un numero finito di vertici, gli enunciati precedenti sono equivalenti ai due che seguono:

  • è connesso e possiede spigoli.
  • è aciclico (senza cicli) e possiede 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 si definisce albero di copertura di un albero tale che e è un sottoinsieme di Se 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.

Il livello di un nodo in un albero è uguale 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.

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

Ogni albero binario con foglie ha un'altezza maggiore o uguale a

Dimostrazione

[modifica | modifica wikitesto]

Procedendo per induzione sul numero di foglie dell'albero considerato si ha che se la proprietà è banalmente verificata ( 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 tale che e consideriamo un albero binario con foglie di altezza minima. Siano e i due sottoalberi che hanno per radice i figli della radice di Si osserva che ciascuno di questi ha meno foglie tra i due e ne possiede almeno (nel caso di numero pari). Allora per ipotesi di induzione l'altezza di quest'ultimo è maggiore o uguale a quindi anche l'altezza di è certamente maggiore o uguale a .

Lunghezza del cammino

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

Gli alberi (o meglio le classi di isomorfismo degli alberi) quindi si possono disporre su diversi livelli caratterizzati dal numero 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 si trovano tutti e soli gli alberi con spigoli che con il processo di riduzione visto sopra si riducono al grafo nodo con passi nei quali diminuisce di uno il numero degli spigoli.

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

Arricchimenti degli alberi

[modifica | modifica wikitesto]

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 vertici sono gli interi da 1 ad

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.

  • Ogni albero è un grafo planare e un grafo bipartito.
  • Ogni grafo connesso ammette un sottoalbero ricoprente, cioè un sottografo che è un albero e che contiene tutti vertici di
  • Dati vertici etichettati (e distinguibili), ci sono modi diversi per collegarli per trasformarli in un albero. Questo risultato è chiamato formula di Cayley.
  • Il numero degli alberi con vertici di grado è
Questo è chiamato coefficiente multinomiale.
  • Non è nota alcuna espressione chiusa per il numero degli alberi astratti con vertici, ossia il numero delle classi di isomorfismo di alberi. È però noto il comportamento asintotico di : esistono due numeri e tali che
  • Ogni albero con un numero maggiore o uguale a 2 nodi possiede almeno 2 foglie.
  • Ogni albero con nodi possiede 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

[modifica | modifica wikitesto]

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

Un albero binario con nodi interni ha 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 Per un qualsiasi albero binario con nodi interni ha 1 nodo interno nel sottoalbero destro ed nel sottoalbero sinistro essendo la radice un nodo interno. Per induzione, il sottoalbero sinistro ha nodi esterni mentre il destro ne ha per un totale di

Un albero binario con nodi interni ha archi: archi interni e 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 archi che connettono nodi interni. Similmente ciascuno degli 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

[modifica | modifica wikitesto]
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

[modifica | modifica wikitesto]

Un albero con radice è una coppia dove è un albero e 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 in un albero con radice c'è un unico cammino semplice da a (se ); il vertice che precede il vertice è detto padre di

Albero ordinato

[modifica | modifica wikitesto]

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: (definiti su insiemi di vertici disgiunti) e è un nodo diverso dai nodi di allora la sequenza è un albero ordinato.[k cosa sarebbe?]

Albero binario

[modifica | modifica wikitesto]

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 di un albero binario, il sottoalbero che ha come radice il figlio sinistro di se esiste, sarà detto sottoalbero sinistro di

Albero binario completo di altezza h

[modifica | modifica wikitesto]

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 risulta essere:

e quindi

per

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

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

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
Controllo di autoritàLCCN (ENsh85137259 · GND (DE4004849-4 · J9U (ENHE987007548784505171
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica