Albero ricoprente minimo

Nella teoria dei grafi, dato un grafo con archi pesati, l'albero ricoprente minimo o albero di copertura di costo minimo (in inglese minimum spanning tree, in sigla MST)^[1] è un albero ricoprente nel quale sommando i pesi degli archi si ottiene un valore minimo.

Definizione formale

Dato un grafo $G=(N,A)$ non orientato, 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 tale che:^[2]

w(MST)=\min _{MST\in S}\sum _{(u,v)\in MST}w(u,v).

Dove $S$ è l'insieme di tutti gli alberi ricoprenti $T$ di $G$ , ovvero l'insieme di tutti i suoi sottografi che rispettano le seguenti condizioni:

$T\subseteq A$ , quindi $T$ contiene solo una parte degli archi originali, al limite tutti, ma non di più.
$(N,T)$ è connesso: i nodi sono tutti collegati tra loro.

Modello matematico

Dato un grafo $G=(N,A)$ non orientato e connesso con costi $c_{i,j}$ associati agli archi e vettore dei flussi sugli archi

x_{i,j}={\begin{cases}1,&{\text{se l'albero contiene l'arco }}(i,j),\\0,&{\text{altrimenti}}.\end{cases}}

Un albero di copertura di costo minimo (MST) è la soluzione del seguente modello matematico^[3]

${\begin{aligned}&\min \sum _{(i,j)\in A}c_{ij}x_{ij},\\&\sum _{(i,j)\in A}x_{ij}=n-1\quad {\text{(vincolo grafo connesso)}},\\&\sum _{i\in S,j\in S}x_{ij}\leqslant |S|-1,\qquad \forall S\subseteq A,|S|\geqslant 3\quad {\text{(vincolo assenza di cicli nel grafo)}},\end{aligned}}$

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

è un sottoinsieme di $A$ (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à:

\sum _{i\in S,j\notin S}x_{ij}+\sum _{i\notin S,j\in S}x_{ij}\geqslant 1,\qquad \forall S\subseteq N\quad {\text{(vincolo nodi connessi)}}.

Condizioni di ottimalità

L'albero di copertura di costo minimo $T$ che si ottiene applicando un algoritmo risolutivo è ottimo se rispetta le seguenti condizioni:

sui cicli: $T$ è un albero di copertura di costo minimo $\quad \Leftrightarrow \quad \forall (u,v)\notin T\quad c_{u,v}\geq c_{i,j},\ \forall (i,j)$ in un cammino da $u$ a $v$ in $T$ ;
sui tagli: $T$ è un albero di copertura di costo minimo $\quad \Leftrightarrow \quad \forall (u,v)\in T\quad c_{u,v}\leq c_{i,j},\ \forall (i,j)$ in un taglio formato eliminando l'arco $(u,v)$ da $T$ .

Algoritmi per il calcolo di un MST

Algoritmo generico

L'algoritmo generico per la costruzione di un albero ricoprente minimo è di tipo greedy.^[1] Dato un grafo $G=(V,E)$ non orientato, connesso e con una funzione peso $w\colon 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.^[2]

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

Trovare l'arco corretto

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:

un arco $(u,v)$ attraversa un taglio $(S,V-S)$ se e solo se $u\in S\land v\in (V-S)$ .
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.

Dato un insieme $A$ di archi contenuto in qualche albero di connessione minima, sia $(S,V-S)$ un taglio che rispetta $A$ e sia $a=(u,v)$ un arco leggero, allora l’arco $a$ è sicuro (safe-edge).

Algoritmi usati nella pratica

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

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.^[4]

Altre applicazioni pratiche basate sugli Alberi Ricoprenti Minimi:

Tassonomia.^[5]
Clustering: clustering dei punti nel piano,^[6]
Costruzione degli alberi per il broadcasting nelle reti di computer.^[7]
Feature extraction curvilinea in computer vision.^[8]
Riconoscimento della scrittura per espressioni matematiche.^[9]
Regionalizzazione di aree socio-geografiche, ovvero raggruppare delle aree in regioni omogenee e contigue.^[10]
Gli Alberi ricoprenti minimi possono essere utilizzati per descrivere i mercati finanziari.^[11]^[12] 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

^ ^a ^b Goodrich-Tamassia, p. 564.
^ ^a ^b (EN) Samuel J. Lomonaco , Jr., Minimal-Spanning-Trees (PDF), su csee.umbc.edu, Università del Maryland - Dipartimento di ingegneria informatica ed elettrica. URL consultato il 2 gennaio 2017.
^ G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
^ R. L. Graham e Pavol Hell, On the history of the minimum spanning tree problem, in Annals of the History of Computing, vol. 7, n. 1, 1985, pp. 43–57, DOI:10.1109/MAHC.1985.10011, MR 783327.
^ P. H. A. Sneath, The Application of Computers to Taxonomy, in Journal of General Microbiology, vol. 17, n. 1, 1º agosto 1957, pp. 201–226, DOI:10.1099/00221287-17-1-201, PMID 13475686.
^ T. Asano, B. Bhattacharya, M. Keil e F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Fourth Annual Symposium on Computational Geometry (SCG '88), vol. 1, 1988, pp. 252–257, DOI:10.1145/73393.73419.
^ Yogen K. Dalal e Robert M. Metcalfe, Reverse path forwarding of broadcast packets, in Communications of the ACM, vol. 21, n. 12, 1º dicembre 1978, pp. 1040–1048, DOI:10.1145/359657.359665.
^ Minsoo Suk e Ohyoung Song, Curvilinear feature extraction using minimum spanning trees, in Computer Vision, Graphics, and Image Processing, vol. 26, n. 3, 1º giugno 1984, pp. 400–411, DOI:10.1016/0734-189X(84)90221-4.
^ Ernesto Tapia e Raúl Rojas, Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance (PDF), in Graphics Recognition. Recent Advances and Perspectives, Lecture Notes in Computer Science, vol. 3088, Berlin Heidelberg, Springer-Verlag, 2004, pp. 329–340, ISBN 978-3-540-22478-5.
^ R. M. AssunÇão, M. C. Neves, G. Câmara e C. Da Costa Freitas, Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees, in International Journal of Geographical Information Science, vol. 20, n. 7, 2006, pp. 797–811, DOI:10.1080/13658810600665111.
^ 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.

Bibliografia

Michael T. Goodrich, Roberto Tamassia, Strutture dati e algoritmi in Java, Bologna, Zanichelli Editore, 2007, pp. 562-565, ISBN 978-88-08-07037-1.

Altri progetti

Wikibooks contiene testi o manuali sull'albero ricoprente minimo
Wikimedia Commons contiene immagini o altri file sull'albero ricoprente minimo

Collegamenti esterni

(EN) Eric W. Weisstein, Minimum Spanning Tree, su MathWorld, Wolfram Research.
(EN) Minimum spanning tree, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Portale Informatica

Portale Matematica

[Goodrich-Tamassia-564-1] Goodrich-Tamassia, p. 564.

[umbc-2] (EN) Samuel J. Lomonaco , Jr., Minimal-Spanning-Trees (PDF), su csee.umbc.edu, Università del Maryland - Dipartimento di ingegneria informatica ed elettrica. URL consultato il 2 gennaio 2017.

[3] G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa

[4] R. L. Graham e Pavol Hell, On the history of the minimum spanning tree problem, in Annals of the History of Computing, vol. 7, n. 1, 1985, pp. 43–57, DOI:10.1109/MAHC.1985.10011, MR 783327.

[5] P. H. A. Sneath, The Application of Computers to Taxonomy, in Journal of General Microbiology, vol. 17, n. 1, 1º agosto 1957, pp. 201–226, DOI:10.1099/00221287-17-1-201, PMID 13475686.

[6] T. Asano, B. Bhattacharya, M. Keil e F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Fourth Annual Symposium on Computational Geometry (SCG '88), vol. 1, 1988, pp. 252–257, DOI:10.1145/73393.73419.

[7] Yogen K. Dalal e Robert M. Metcalfe, Reverse path forwarding of broadcast packets, in Communications of the ACM, vol. 21, n. 12, 1º dicembre 1978, pp. 1040–1048, DOI:10.1145/359657.359665.

[8] Minsoo Suk e Ohyoung Song, Curvilinear feature extraction using minimum spanning trees, in Computer Vision, Graphics, and Image Processing, vol. 26, n. 3, 1º giugno 1984, pp. 400–411, DOI:10.1016/0734-189X(84)90221-4.

[9] Ernesto Tapia e Raúl Rojas, Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance (PDF), in Graphics Recognition. Recent Advances and Perspectives, Lecture Notes in Computer Science, vol. 3088, Berlin Heidelberg, Springer-Verlag, 2004, pp. 329–340, ISBN 978-3-540-22478-5.

[10] R. M. AssunÇão, M. C. Neves, G. Câmara e C. Da Costa Freitas, Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees, in International Journal of Geographical Information Science, vol. 20, n. 7, 2006, pp. 797–811, DOI:10.1080/13658810600665111.

[11] Mantegna, R. N. (1999). Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193-197.

[12] Djauhari, M., & Gan, S. (2015). Optimality problem of network topology in stocks market analysis. Physica A: Statistical Mechanics and Its Applications, 419, 108-114.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]