Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 28/04/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Minimo Albero Ricoprente
Sia G=(V,E) un grafo connesso non orientato e w:ER una
funzione costo degli archi di G. Definiamo inoltre m:VV
nel seguente modo: m(u)=v sse (u,v) è l’arco di costo minimo
incidente su u.
Un albero ricoprente (ST) di G=(V,E) è un albero T=(V,E')
tale che E'E.
Un minimo albero ricoprente (MST) di G=(V,E) è un albero
ricoprente T=(V,E') di costo minimo.
Il costo di un albero è la somma dei costi degli archi che lo
compongono: w(T)=eT w(e).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Unicità del MST
Il MST è unico sse ogni arco ha un costo distinto. Tale
condizione può essere forzata disambiguando eventuali costi
uguali: si aggiunge al costo l’indice dell’arco cui appartiene:
w'(e) = <w(e),e>
a
<1,e1>
b
<5,e4>
a
<1,e1>
<6,e2>
<3,e8>
<2,e3>
<1,e9>
d
<2,e3>
b
e
d
<2,e5>
<5,e6>
c
<2,e7>
<1,e9>
e
<2,e5>
c
Si noti che tra <2,e5> e <2,e7> viene scelto <2,e5>
Nel seguito i costi verranno sempre disambiguati considerando gli archi
indicizzati in base al loro ordine lessicografico.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Proprietà 1
Lemma1. Tutti gli archi (u,m(u))MST.
Dimostrazione. Sia G=(V,E) un grafo, w una funzione di
costo su G e T il MST di G. Assumiamo per assurdo che
esista un vV tale che (v,m(v))T.
Consideriamo il cammino da v a m(v) in T sia (v,x) il primo
arco in tale cammino. Il costo di tale arco è sicuramente
maggiore di quello dell’arco (v,m(v)), per definizione di m(v).
Sia T' = T - (v,x)  (v,m(v)). T' è un albero ricoprente per G e
il suo costo w(T')=w(T)-w(v,x)+(v,m(v)) è minore di quello di
T, il che contrasta con il fatto che T è il MST di G, quindi v
non può esistere.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Stelle ed alberi radicati
Stella Radicata
Albero Radicato
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Pseudoforesta
Si definisce pseudoforesta un grafo orientato in cui ogni vertice ha grado
uscente minore od uguale ad uno. In altre parole, pseudoforesta è un
insieme di alberi (e stelle) orientati radicati, ciascuno contenente un ciclo.
18
4
6
14
13
20
1
8
2
3
16
19
5
10
12
11
17
7
15
21
9
Una pseudoforesta può essere vista come una funzione d:VV.
vV, (v,d(v)) è l’unico arco uscente da v in G.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
d(v)
14
13
20
21
10
6
2
13
10
20
8
1
4
18
2
20
8
1
3
6
2
6
Proprietà 2
La funzione m:VV definisce una pseudoforesta t.c. ogni
albero orientato ha un ciclo contenente esattamente due archi.
Non ci sono cappi perché m(u)u uV. Se per assurdo ci
fosse un ciclo di 3 (o più archi) tra i nodi u, v=m(u) e x=m(v)
con u=m(x) allora considerando i costi di tali archi w1, w2 e
w3 si avrebbe w1 < w3 < w2 < w1. Il che è assurdo.
w1
u
v
w3
w2
x
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Strategie per MST
Prim: si parte da T = un singolo vertice e si costruisce
incrementalmente il MST aggiungendo l’arco di costo
minimo tra T e G-T.
Kruskal: si parte da una foresta di nodi isolati e,
considerando tutti gli archi in ordine di costo crescente, si
aggiunge ciascun arco solo se non induce un ciclo.
Sollin: si parte da una foresta di nodi isolati, si aggiungono
tutti gli archi (u,m(u)) e si itera fino ad ottenere un grafo
connesso.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Esempio 1
1
d
A partire dal grafo
1
3
1
1
c
f
b
4
2
2
1
a
e
2
1
g
Prim inizia con T=({a},). Poi inserisce, passo dopo passo,
gli archi (a,g), (g,e), (a,b), (b,d), (b,f) e (d,c). L’albero
ricoprente generato è:
d
f
1
1
1
c
e
b
2
a
1
Algoritmi Paralleli e Distribuiti a.a. 2008/09
1
g
9
Esempio 2
Kruskal genera il medesimo MST analizzando gli archi nel
seguente ordine (quelli che inducono cicli vengono scartati):
e
(a,g)
(b,d)
(b,f)
(c,d)
(d,f)
(e,g)
(a,b)
(a,c)
(f,g)
(e,f)
(b,g)
w(e) induce un ciclo?
1
no
1
no
1
no
1
no
1
si
1
no
2
no
2
si
2
si
3
si
4
si
d
f
1
1
1
c
e
b
2
a
Algoritmi Paralleli e Distribuiti a.a. 2008/09
1
1
g
10
Esempio 3
Sollin inizialmente considera i seguenti archi:
v
a
b
c
d
e
f
g
m(v) costo
g
1
d
1
d ottiene:
1
ed
b
1
g
1
b
1
a
1
d
f
1
1
1
c
e
b
1
1
a
g
In seguito considera gli archi tra le due componenti connesse:
V
C1
C2
m(V)
C2
C1
costo arco originale
2
(a,b)
2
(a,b)
d
f
1
1
1
c
e
b
2
a
Algoritmi Paralleli e Distribuiti a.a. 2008/09
1
1
g
11
Strategia per il concorrente
Sia Prim che Kruskal sono inerentemente sequenziali in
quanto la scelta fatta ad ogni passo dipende strettamente da
tutto ciò che si è fatto nei passi precedenti.
L’idea di Sollin invece (ad ogni iterazione) lavora su tutti i
vertici senza richiedere un ordine specifico, quindi si presta
meglio ad essere utilizzata in un contesto di calcolo
concorrente (sia parallelo che distribuito).
Si noti però che se i costi non fossero distinti con Sollin si
potrebbero introdurre cicli di lunghezza ≥ 3:
1
a
b
1
1
c
u m(u)
a b
b c
c a
b
a
Algoritmi Paralleli e Distribuiti a.a.2007/08
c
12
MST nel concorrente
Input: G grafo non orientato connesso pesato, con pesi
distinti
Output: l’unico MST
Idea: partendo da frammenti costituiti da singoli nodi, ad
ogni passo ogni frammento cerca di unirsi con un altro
frammento attraverso lo spigolo di costo minimo ad esso
incidente. Si ripete finché la foresta non si riduce ad un
albero.
Algoritmi Paralleli e Distribuiti a.a.2007/08
13
Come fare
• Identificare l’adiacente di costo minimo
• Rappresentare e identificare opportunamente i frammenti
• Fondere i frammenti avendo presente le limitazioni sul
costo (tempo, processori, complessità dei messaggi) che si
vuole ottenere
Algoritmi Paralleli e Distribuiti a.a.2007/08
14