Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 19.Il Problema dell'Albero di Copertura Minimo (MST)


Il Problema dell’Albero di Copertura Minimo, 1

Sia dato un grafo non orientato e connesso G=(V,E), |V|=n, |E|=m, e ad ogni arco [i,j] in E sia assegnato un costo c_{ij} .

Per ogni sottoinsieme E’ non proprio di E, il costo complessivo c(E’) associato ad E’ è così definito:
\[ c(E')=\displaystyle{\sum_{[i,j]\in E'}c_{ij}}. \]

Il Problema dell’Albero di Copertura Minimo (Minimum Spanning Tree – MST) di G consiste nell’individuare un albero T_G=(V,E') che “ricopra” G e che fra tutti gli alberi ricoprenti G sia un albero di costo totale minimo.

Il Problema dell’Albero di Copertura Minimo, 2

Alcune semplici considerazioni utili alla completa comprensione del problema:

  • l’insieme dei nodi dell’albero T_G=(V,E') coincide con l’insieme dei nodi del grafo G, per cui l’insieme degli archi E’ di T_G ha cardinalità pari a |V|-1=n-1.
  • affermare che T_G=(V,E') sia un albero di copertura minimo per G vuole dire affermare che \[ c(E')\leq c(\hat E),\ \mbox{per ogni}\ \hat T_G=(V,\hat E)\ \mbox{albero di copetura di}\ G . \]
  • se G=(V,E) non è connesso, il problema MST non ammette soluzione.

Formulazione matematica dell’MST, 1

Definiamo le seguenti m variabili di decisione
\[ \forall\ [i,j]\in E,\ \ x_{ij}=\left\{ \begin{array}{lll} 1,   & \mbox{{\rm se $[i,j]\in E'$;}} \\  0,   & \mbox{{\rm altrimenti.}}     \end{array}  \right .  \]

Dal momento che l’obiettivo è minimizzare il costo totale degli archi appartenenti a T_G , la funzione obiettivo è
\[ \displaystyle{\min\sum_{[i,j]\in E}c_{ij}x_{ij}}. \]

Per definire i vincoli del problema è sufficiente imporre la validità delle proprietà di albero che la coppia T_G=(V,E') deve godere, dove E'=\left\{[i,j]\in E\ \vert\ x_{ij}=1\right\} .

Formulazione matematica dell’MST, 2

Infatti, T_G=(V,E') è un albero se

\vert E'\vert=n-1\Longrightarrow\displaystyle{\sum_{[i,j]\in E}x_{ij}=n-1} ;

T_G\ \mbox{aciclico} \Longrightarrow\displaystyle{\sum_{[i,j]\in E(S)}x_{ij}\leq\vert S\vert-1} , \forall\ S\subseteq V , S\not=\emptyset , dove
\[ E(S)=\{[i,j]\in E\ \vert\ i,j\in S\}. \]

Nota: Gs=(S,E(S)) è il sottografo di G indotto da S.

Formulazione matematica dell’MST, 3

Riassumendo, il Problema del Minimum Spanning Tree di un grafo non orientato ha la seguente formulazione matematica:

\[  \begin{array}{llll} \mbox{(MST)} & \mbox{{\rm min}} & \displaystyle{\sum_{[i,j]\in E} c_{ij}x_{ij}}\\ \\ & \mbox{{\rm s.a}} \\ \\ & \mbox{{\rm (a)}}    & \displaystyle{\sum_{[i,j]\in E}x_{ij}} = n-1 &  \\ \\ & \mbox{{\rm (b)}}    & \displaystyle{\sum_{[i,j]\in E(S)}x_{ij}} \leq \vert S\vert-1, & \forall\ S\subseteq V, S\not=\emptyset \\ \\ &        & x_{ij}\in\{0,1\}, & \forall\ [i,j]\in E. \end{array} \]

In quanto segue, sarà descritto un algoritmo esatto polinomiale che segue una strategia di tipo greedy per individuare un albero di copertura minimo di un grafo non orientato.

Algoritmo di Kruskal, 1

L’algoritmo di Kruskal è un algoritmo polinomiale che seguendo una strategia di tipo greedy individua un albero di copertura minimo di un grafo non orientato.

Una qualunque tecnica di tipo greedy costruisce una soluzione al problema a partire da una soluzione vuota, aggiungendo di volta in volta alla soluzione parziale in costruzione l’elemento candidato più conveniente in termini di valore di funzione obiettivo (nel caso dell’MST, detto elemento sarà un arco del grafo).

Come già sottolineato, non tutti i problemi di ottimizzazione possono essere risolti all’ottimo applicando questa strategia, ma solo quelli per i quali sia possibile dimostrare che effettuare la scelta migliore al momento conduce ad una soluzione ottima globale.

Algoritmo di Kruskal, 2

Dato un albero T_G=(V,E') ed un arco [i,j]\notin E' , in quanto segue indicheremo con {\mathcal C}[E',[i,j]] l’insieme degli archi che formano un ciclo in E'\cup\{[i,j]\} .
Inoltre, supporremo che

  1. G=(V,E) sia connesso: se G non fosse connesso, il problema non ammetterebbe soluzione;
  2. c_{ij}\not=c_{hk},\ \forall\ [i,j],\ [h,k]\in E,\ [i,j]\not=[h,k].

L’ipotesi 2. serve a garantire l’unicità dell’albero di copertura a costo minimo di G ed è utile solo a semplificare la
dimostrazione del seguente teorema enunciato nella slide successiva.
Infatti, rimuovendo l’ipotesi 2, gli algoritmi proposti a soluzione esatta del problema risultano ancora validi ed individuano una delle soluzioni ottime.

Algoritmo di Kruskal, 3

Teorema.

Sia T_G=(V,E') un MST per G=(V,E). Per ogni arco [i,j] di E si ha che

\[ [i,j]\in E' \Longleftrightarrow \exists\ S\subset V\ \mbox{tale che}\ [i,j]=\mbox{{argmin}}\{c_{vw}\ \vert\ [v,w]\in \delta_G(S)\}, \

dove
\[ \delta_G(S)=\{[v,w]\in E\ \vert\ v\in S,\ w\in V\setminus S\} \]
ed è detto taglio di G rispetto ad S.

Algoritmo di Kruskal, 4

Dimostrazione “⇐”
Supponiamo per assurdo che [i,j]\notin E' . In E'\cup\{[i,j]\} si formerà un ciclo {\mathcal C}[E',[i,j]] che attraversa il taglio \delta_G(S) almeno due volte (vedi Figura).
Si noti che c_{ij}<c_{hk} , per cui l’albero di copertura di G dato da
\[ \hat T_G=(V,\hat E),\ \mbox{con}\ \hat E=E'\setminus\{[h,k]\}\cup\{[i,j]\} \]
avrà costo totale
\[ c(\hat E)=c(E')-c_{hk}+c_{ij}<c(E'). \]
Si giunge, quindi, ad un assurdo, essendo T_G un MST per G per ipotesi.

Nella figura a lato: Ciclo {\mathcal C}[E',[i,j]] in E'\cup\{[i,j]\} ; c_{ij}<c_{hk} , per ipotesi).

Minimum Spanning Tree. Disegnata da Paola Festa

Minimum Spanning Tree. Disegnata da Paola Festa


Algoritmo di Kruskal, 5

Dimostrazione “⇒”
Per ipotesi, [i,j] è un arco dell’MST T_G e
dobbiamo verificare che esiste un sottoinsieme proprio S tale che [i,j] sia un arco di costo minimo fra tutti gli archi attraversanti il taglio \delta_G(S) .

Si scelga come S una delle due componenti connesse che si ottengono rimuovendo da E’ l’arco [i,j] (vedi Figura) e si supponga per assurdo che esista un arco [v,w] nell’insieme \delta_G(S)\setminus\{[i,j]\} tale che c_{vw}<c_{ij} .
In tali ipotesi, è possibile costruire un albero di copertura alternativo dato

\[ \hat T_G=(V,\hat E),\ \mbox{con}\ \hat E=E'\setminus\{[i,j]\}\cup\{[v,w]\}, \]
Cui è associato un costo totale pari

\[ c(\hat E)=c(E')-c_{ij}+c_{vw}<c(E'). \]

Ma ciò contraddice l’ipotesi di ottimalità di T_G .

Minimum Spanning Tree. Disegnata da Paola Festa

Minimum Spanning Tree. Disegnata da Paola Festa


Algoritmo di Kruskal, 6

Il Teorema appena enunciato e dimostrato suggerisce un semplice algoritmo greedy per trovare una soluzione ottima al Problema dell’MST di un grafo: l’algoritmo di Kruskal.

In fase di inizializzazione gli archi del grafo vengono ordinati per valori non decrescenti dei rispettivi costi ed il grafo
viene considerato come una foresta di n componenti connesse C_i,\ i=1,2,\ldots,n , ciascuna contenente il solo nodo i. T_G=(V,E'),\ E'=\emptyset .

Ad ogni iterazione viene selezionato l’arco [i,j] avente il costo correntemente minimo e viene aggiunto all’MST in costruzione solo se esso non forma cicli con gli archi già selezionati, ossia se i suoi nodi estremi non appartengono già alla stessa componente connessa.

Nota: [i,j] è l’arco di costo minimo in \delta_G(S) , con S=C_i (o S=C_j ).

Algoritmo di Kruskal, 7

\fbox{\begin{minipage}[h]{13cm} \footnotesize{ \begin{tt} {\bf algoritmo} {kruskal} ($V$,$E$)\\ $1$\hspace*{0.5truecm} $W_{\mbox{tot}}:=0$; $k:=0$; $h:=0$;\\ $2$\hspace*{0.5truecm} Ordina e memorizza in $L$ gli archi per valore non decrescente dei \\ \hspace*{0.7truecm} costi; \\ $3$\hspace*{0.5truecm} {\bf for} $q=1$ {\bf to} $n$ {\bf do} $C[q]:=q$; \mbox{/* una componente connessa per ogni nodo */} \\ $4$\hspace*{0.5truecm} {\bf while} ( ($k<br />
$5$\hspace*{1truecm} $h:=h+1$; $[i,j]:=L[h]$; $C_1:=C[i]$; $C_2:=C[j]$; \\ $6$\hspace*{1truecm} {\bf if}  ($C_1\not=C_2$) {\bf then} \hspace*{0.8truecm} \mbox{/* $[i,j]$ pu\`o essere selezionato */} \\ $7$\hspace*{1.5truecm} $W_{\mbox{tot}}:=W_{\mbox{tot}}+c_{ij}$; $k:=k+1$; $E'[k]:=[i,j]$; \\ $8$\hspace*{1.5truecm} {\bf for} $q=1$ {\bf to} $n$ {\bf do} \hspace*{0.3truecm} \mbox{/* unione delle componenti $C_1$ e $C_2$ */} \\ $9$\hspace*{2truecm} {\bf if} ($C[q]=C_2$) {\bf then} $C[q]:=C_1$; \\ $10$\hspace*{1.3truecm} {\bf endfor} \\ $11$\hspace*{0.8truecm} {\bf endif} \\ $12$\hspace*{0.3truecm} {\bf endwhile} \\ $13$\hspace*{0.3truecm} {\bf if} ($k=n-1$) {\bf then} {\bf return} ($E'$, $W_{\mbox{tot}}$);\\ $14$\hspace*{0.3truecm} {\bf else} print \lq\lq Il grafo non \`e connesso\rq\rq \\ {\bf end} {kruskal} \end{tt} } \end{minipage}}

Complessità computazionale dell’algoritmo di Kruskal

L’ordinamento degli archi in fase di inizializzazione (linea 2) richiede

\[ O(\vert E\vert\log \vert E\vert)=O(m\log m)=O(m\log n), \]
dato che m< n^2 .

L’aggiornamento delle componenti (linee 8 e 9) richiede O(n) e viene effettuato al più n-1 volte.
Dunque, il loop while (linee 4–12) richiede O(n^2) .

Ne consegue che la complessità dell’algoritmo di Kruskal è

\[ O(m\log n+n^2). \]

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion