Home

Federica EU

1/13

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

G=(V,E) sia connesso: se G non fosse connesso, il problema non ammetterebbe soluzione;
$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

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

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)$ .