Albero ricoprente
Da Wikipedia, l'enciclopedia libera.
Un albero ricoprente o albero di connessione 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 è meglio noto con il termine inglese Spanning tree (ST).
Indice |
[modifica] Albero ricoprente minimo
Nel caso in cui gli archi siano pesati si può definire anche l' Albero ricoprente minimo, o Minimum spanning tree (MST), essere l'albero di connessione di peso minimo, dove il peso è la somma dei pesi di tutti gli archi che appartengono a tale albero.
[modifica] Algoritmi
Dato un grafo esistono diversi algoritmi per individuare un suo MST, tra questi:
che viene specializzato per implementare
- Algoritmo di Boruvka
[modifica] Applicazioni
Il concetto di albero ricoprente viene utilizzato nelle reti locali, vedi anche Spanning tree (networking).
[modifica] Foresta ricoprente minima
Nel caso in cui il grafo non sia connesso, cioè sia il risultato dell'unione di più grafi connessi, si può ancora definire una Foresta ricoprente minima come l'unione degli alberi ricoprenti individuati sui singoli grafi connessi. In grafi connessi foresta ed albero ricoprente coincidono.
