Albero ricoprente

Grafo con evidenziato un Albero spanning — Grafo con evidenziato un **Albero spanning**

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).

Definizione formale

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).

Proprietà

Seguono alcune delle proprietà principali di un albero ricoprente.^[1]

Possiede $n-1$ archi, dove $n$ è 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.