Albero ricoprente

Da Wikipedia, l'enciclopedia libera.
Grafo con evidenziato un Albero spanning

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, 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 è anche noto con il termine inglese spanning tree (ST).

Albero ricoprente minimo[modifica | modifica wikitesto]

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 un valore minimo.

Definizione formale[modifica | modifica wikitesto]

Dato un grafo G=(V,E) indiretto, connesso e pesato e assumendo che w(u,v)\in \mathbb{R}^+ sia una funzione peso per G.

Un MST per G è un insieme di archi T che forma un albero, cioè tale che:

  • T \subseteq E, quindi T contiene solo una parte degli archi originali, al limite tutti, ma non di più.
  • (V,T) è connesso: i nodi sono tutti collegati tra loro.
  • La somma dei pesi degli archi scelti è la più piccola possibile, cioè: w(T)=\sum_{(u,v)\in T}w(u,v) è minima.

Dalla definizione, si ha che T forma un albero con un sottoinsieme di archi dai pesi minimi, per questo viene chiamato Minimum Spanning Tree.

Algoritmi per il calcolo di un MST[modifica | modifica wikitesto]

Algoritmo generico[modifica | modifica wikitesto]

Dato un grafo G=(V,E) non orientato, connesso e con una funzione peso w:E\rightarrow\mathbb{R}^+, l'algoritmo agisce su un insieme A\subseteq T (con T MST di G) al quale ad ogni passo viene aggiunto un arco (u,w) che permette ad A di restare un sottoinsieme del MST finale, un tale arco verrà chiamato safe-edge.

  1. A\leftarrow\emptyset
  2. while A \neq T do
    1. (u,v)\leftarrow safe-edge(A)
    2. A\leftarrow A \cup (u,v)
  3. end while
  4. return A

Trovare l'arco corretto[modifica | modifica wikitesto]

Per trovare l'arco corretto è necessario ricorrere ad alcune definizioni:

Per prima cosa (S,V-S) con S\subseteq V verrà chiamato taglio, e avremo che:

  1. un arco (u,v) attraversa un taglio (S,V-S) se e solo se u\in S \and v \in (V-S).
  2. un albero A \subseteq E rispetta un taglio (S,V-S) se e solo se \not\exists (u,v) \in A che attraversa il taglio.

Un arco (u,v) viene definito leggero rispetto ad un taglio (S,V-S), se è di peso minimo tra tutti gli archi che attraversano quel taglio.

Preso un grafo G=(V,E) non orientato e connesso, una funzione di peso w: E\rightarrow R^+, un albero A \subseteq T con T MST per G ed infine un taglio (S,V-S) di G ed A.

Allora (u,v) è un safe-edge per A.

Algoritmi usati nella pratica[modifica | modifica wikitesto]

Dato un grafo esistono diversi algoritmi per individuare un suo MST, tra questi:

che viene specializzato per implementare i seguenti algoritmi:

Applicazioni[modifica | modifica wikitesto]

Il concetto di albero ricoprente viene utilizzato nelle reti locali, vedi anche Spanning tree (networking).

Foresta ricoprente minima[modifica | modifica wikitesto]

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.

Voci correlate[modifica | modifica wikitesto]