Albero ricoprente

Da Wikipedia, l'enciclopedia libera.
Grafo con evidenziato un Albero spanning

Un albero di copertura o albero di connessione o albero di supporto di un grafo, connesso e con archi non orientati, è un albero che contiene tutti i vertici del grafo, ma degli archi ne contiene soltanto un sottoinsieme, cioè solo quelli necessari per connettere tra loro tutti i vertici con uno e un solo cammino. Infatti ciò che differenzia un grafo da un albero è che in quest'ultimo non sono presenti cammini multipli tra due nodi, nell'immagine sono mostrati in grassetto gli archi che fanno parte di un albero ricoprente mentre gli archi del grafo originario erano tutti gli archi, sia quelli in grassetto che quelli sottili.

L'albero ricoprente è anche noto con il termine inglese spanning tree (ST).

Definizione formale[modifica | modifica wikitesto]

Albero ricoprente minimo[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Albero ricoprente minimo.

Nel caso in cui gli archi siano pesati si può definire anche l'albero ricoprente minimo, o minimum spanning tree (MST). Un MST non è altro che un albero ricoprente nel quale sommando i pesi degli archi si ottiene un valore minimo.

Applicazioni[modifica | modifica wikitesto]

Il concetto di albero ricoprente viene utilizzato nelle reti locali, vedi anche Spanning tree (networking).

Voci correlate[modifica | modifica wikitesto]