Albero ricoprente
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.
|
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 e contiene soltanto un sottoinsieme degli archi, 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 sia quelli sottili.
L'albero ricoprente è anche noto con il termine inglese spanning tree (ST).
Definizione formaleModifica
ProprietàModifica
Seguono alcune delle proprietà principali di un albero ricoprente.[1]
- Possiede archi, dove è il numero dei vertici.
- Possiede un numero di archi minimale per la proprietà di connessione: rimuovendo un arco qualsiasi, il grafo non è più connesso.
- Possiede un numero di archi massimale per la proprietà di aciclicità: aggiungendo un arco fra due vertici qualsiasi, il grafo non è più aciclico.
- All'interno dell'albero esiste un unico cammino semplice fra due nodi.
Albero ricoprente minimoModifica
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 il valore minimo tra tutti i possibili alberi.
ApplicazioniModifica
Il concetto di albero ricoprente viene utilizzato nelle reti locali, vedi anche Spanning tree (networking).
NoteModifica
- ^ (EN) Kevin Wayne, Greedy Algorithms II (PDF), Università di Princeton, Dipartimento di Informatica, 18 febbraio 2013. URL consultato il 13 settembre 2016 (archiviato il 13 settembre 2016).
Voci correlateModifica
Altri progettiModifica
- Wikimedia Commons contiene immagini o altri file su albero ricoprente
Controllo di autorità | LCCN (EN) sh2005003951 |
---|