Albero ricoprente
sottografo di un grafo G non orientato che è un albero ed include tutti i vertici di G Da Wikipedia, l'enciclopedia libera
sottografo di un grafo G non orientato che è un albero ed include tutti i vertici di G Da Wikipedia, l'enciclopedia libera
Un albero ricoprente (anche detto di copertura, di connessione o 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).
Un albero è un particolare tipo di grafo non orientato all'interno del quale non possono esistere percorsi chiusi (grafo aciclico) e per ogni coppia di nodi esiste un unico collegamento che li congiunge (grafo connesso).
Seguono alcune delle proprietà principali di un albero ricoprente.[1]
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.
Il concetto di albero ricoprente viene utilizzato nelle reti locali, vedi anche Spanning tree (networking).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
