Primi elementi della teoria dei grafi

Albero ricoprente

La struttura ad albero, essendo minimale rispetto al numero degli spigoli, rappresenta la soluzione ideale per progettare una rete di collegamento (stradale, telefonica, ferroviaria) o una rete di distribuzione di servizi (acqua, gas, teleriscaldamento) o un circuito elettico. Supponiamo di voler realizzare una rete ferroviaria che colleghi sei città e sono possibili varie soluzioni a secondo della lunghezza dei singoli tratti ferroviari o dei costi di realizzazione. Le varie possibilità sono indicate dal seguente grafo pesato dove i vertici rappresentano le città e gli spigoli le possibili linee ferroviarie con le relative distanze.

Per rendere minima la spesa complessiva bisogna che sia minima la somma delle distanze tra ogni coppia di città e che sia possibile, per un passeggero, andare da ogni città ad ogni altra città. Si tratta quindi di determinare il grafo connesso pesato più economico contenente i sei vertici e il minore numero di spigoli. Un grafo con queste caratteristiche è un grafo ad albero etichettato che è detto albero ricoprente (in inglese spanning tree) o albero di connessione. Esistono vari procedimenti per determinare tale grafo ad esempio è possibile applicare l'algoritmo dell'avaro: si inizia a costruire il tratto più economico e nei passi successivi di aggiungere al tratto precedente quello meno costoso. Applicando questo procedimento si ottiene sempre la soluzione che nel nostro caso specifico ci fornisce il seguente grafo ricopente con peso minimo.

In pratica, un albero ricoprente è un "albero" che ricopre tutti i nodi del grafo originale usando il minor numero possibile di collegamenti. Pertanto gli alberi ricoprenti permettono di semplificare una rete mantenendo la connettività essenziale. Questo è utile in reti di comunicazione: costruire infrastrutture senza cicli ridondanti.