Nella teoria dei grafi, dato un grafo con archi pesati, lalbero ricoprente minimo o albero di copertura di costo minimo (, in sigla MST). è un albero ricoprente nel quale sommando i pesi degli archi si ottiene un valore minimo.

Definizione formale Dato un grafo non orientato, connesso e pesato e assumendo che sia una funzione peso per .

Un MST per è un insieme di archi tale che:

Dove è l'insieme di tutti gli alberi ricoprenti di , ovvero l'insieme di tutti i suoi sottografi che rispettano le seguenti condizioni: , quindi contiene solo una parte degli archi originali, al limite tutti, ma non di più. è connesso: i nodi sono tutti collegati tra loro.

Modello matematico Dato un grafo non orientato e connesso con costi associati agli archi e vettore dei flussi sugli archi

Un albero di copertura di costo minimo (MST) è la soluzione del seguente modello matematicoG. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa

dove è l'insieme degli archi che compongono l'albero di copertura e ha le seguenti proprietà:

è un sottoinsieme di (insieme degli archi del grafo); la cardinalità di tale insieme deve essere almeno uguale a 3 (dato che con meno di 3 elementi in un insieme non si può creare un ciclo).

Il vincolo sull'assenza di cicli nel grafo può essere anche espresso utilizzando il concetto di taglio in un grafo. Il secondo vincolo del modello quindi diventerà:

Condizioni di ottimalità Chiamiamo il coalbero, cioè il complementare dell'albero all'interno del grafo. Ogni lato del grafo lo chiamiamo ramo se fa parte dell'albero e corda se fa parte del coalbero. Un albero di copertura è ottimale (di costo minimo) se e solo se rispetta una condizione di ottimalità. Le due condizioni di ottimalità dui cicli e sui tagli sono equivalenti, osservando che

è nel cammino da a nell'albero è nel taglio formato eliminando l'arco dall'albero

e che i quantificatori di uguale tipo si possono scambiare.

Ottimalità sui cicli Presa una qualsiasi corda nel coalbero, questa determina un unico cammino nell'albero; ogni ramo di tale cammino ha costo minore della corda iniziale.

In formule, , se è nel cammino da a in , allora .

Ottimalità sui tagli Preso un qualsiasi ramo nell'albero e eliminandolo, l'albero si disconnette; ogni corda che ricollega l'albero ha costo maggiore del ramo iniziale.

In formule, , se è nel taglio formato eliminando l'arco da , allora .

Algoritmi per il calcolo di un MST Algoritmo generico L'algoritmo generico per la costruzione di un albero ricoprente minimo è di tipo greedy. Dato un grafo non orientato, connesso e con una funzione peso , l'algoritmo agisce su un insieme (con MST di ) al quale ad ogni passo viene aggiunto un arco che permette ad di restare un sottoinsieme del MST finale, un tale arco verrà chiamato safe-edge.

while do safe-edge

end while return A

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

Per prima cosa con verrà chiamato taglio, e avremo che:

Un arco attraversa un taglio se e solo se . Un albero rispetta un taglio se e solo se che attraversa il taglio.

Un arco viene definito leggero rispetto ad un taglio , se è di peso minimo tra tutti gli archi che attraversano quel taglio.

Dato un insieme di archi contenuto in qualche albero di connessione minima, sia un taglio che rispetta e sia un arco leggero, allora l’arco è sicuro (safe-edge).

Algoritmi usati nella pratica Dato un grafo esistono diversi algoritmi per individuare un suo MST, tra questi: algoritmo di Prim; algoritmo di Kruskal; algoritmo di Borůvka.

Foresta ricoprente minima 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.

Applicazioni Gli spanning tree minimi hanno applicazioni dirette nella progettazione di reti, tra cui reti di computer, reti di telecomunicazioni, reti di trasporto, reti di approvvigionamento idrico e rete elettrica.

Altre applicazioni pratiche basate sugli Alberi Ricoprenti Minimi: Tassonomia. Clustering: clustering dei punti nel piano, Costruzione degli alberi per il broadcasting nelle reti di computer. Feature extraction curvilinea in computer vision. Riconoscimento della scrittura per espressioni matematiche. Regionalizzazione di aree socio-geografiche, ovvero raggruppare delle aree in regioni omogenee e contigue. Gli Alberi ricoprenti minimi possono essere utilizzati per descrivere i mercati finanziari.Mantegna, R. N. (1999). Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193-197.Djauhari, M., & Gan, S. (2015). Optimality problem of network topology in stocks market analysis. Physica A: Statistical Mechanics and Its Applications, 419, 108-114. Una matrice di correlazione può essere creata calcolando un coefficiente di correlazione tra due stocks qualunque. Questa matrice può essere rappresentata topologicamente come una rete complessa ed un albero minimo ricoprente può essere costruito per visualizzarne le relazioni.

Note

Bibliografia

Altri progetti

Collegamenti esterni

Minimo Categoria:Problemi risolvibili in tempo polinomiale