Albero (in teoria dei grafi)
In matematica conviene definire albero un grafo non orientato connesso e privo di cicli.Diciamo invece foresta un grafo non orientato privo di cicli.
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).
Il grafo nodo costituito da un nodo e nessuno spigolo, č un albero (ed anche una foresta).
In una foresta, oltre a eventuali nodi isolati, vi sono sicuramente nodi di valenza 1 che chiamiamo 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. 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 ilgrafo 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.
Abbiamo quindi tre possibili definizioni equivalenti di albero.
Ma se ne possono trovare altre ancora.
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.
Le equivalenze di tutte le definizioni di albero che abbiamo introdotte possono essere dimostrate senza grosse difficoltĂ .
Tutte queste possibili definizioni equivalenti di albero fanno intuire che gli alberi sono grafi di un genere particolarmente interessante che esprimono qualcosa di essenziale. E in effetti si trova che essi hanno varie applicazioni sia all'interno della teoria dei grafi, che in altri settori della matematica (come l'algebra lineare e le algebre di Lie), sia in discipline come la chimica, l'ingegneria strutturale e la organizzazione aziendale.
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 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: queso 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.
