Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 15/05/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Le variabili
Per ogni nodo p:
Fram(p) nome del frammento a cui p appartiene.
Liv(p) valore del livello del frammento a cui p appartiene.
Per ogni arco (p, q):
Statop(q) accettato se è stato inserito nel MST.
Per ogni frammento f:
w(f) minimo fra i costi degli archi uscenti da f (è
sufficiente ad identificare univocamente l’arco perché
assumiamo costi distinti).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Visita inorder
La visita inorder (FS,R,FD) è definita soltanto su alberi binari, ed è
necessario poter distinguere tra figlio sinistro e figlio destro di ogni nodo.
Nelle nostre strutture dati non abbiamo tale informazione quindi
assumeremo che l’albero abbia la proprietà 0/2 (ciascun nodo ha
esattamente 0 o 2 figli).
Per ottenere la numerazione inorder ciascuna foglia viene conteggiata in
corrispondenza della sua unica occorrenza (left=right=1) nel CDE, mentre
i nodi interni vengono conteggiati nell’occorrenza intermedia tra il primo
ed il secondo figlio (left=right=0).
Si da quindi valore 1 a tutti gli archi tali che left=right e si eseguono le
somme prefisse S.
 v inorder(v) = S(u,v)
dove (u,v) è l’arco in cui v è stato conteggiato: left(u,v)=right(u,v).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Esempio di visita inorder
g
a
c
b
f
CDE
g,a a,g
e
d
g,c
c,b
b,f
f,b
b,d d,b
b,c
c,e
e,c
c,g
left 1
0
1
1
1
0
1
0
0
1
0
0
right 1
0
0
0
1
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
1
0
0
S 1
2
2
2
3
4
5
5
6
7
7
7
v a b c d e f g
inorder 1 4 6 5 7 3 2
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
LCA
La computazione del minimo antecedente comune (lca)
di ogni nodo si basa sulle seguenti osservazioni*:
h
e
1.
2.
u è antecedente di v sse left(u) < left(v) < right(u)
u e v sono confrontabili (nessuno è antecedente
dell’altro) sse
right(v) < left(u) oppure right(u) < left(v)
3. se u e v sono confrontabili, lca(u,v) è il vertice di livello
più basso compreso tra right(u) e left(v)
h,e
e,h
h,c
c,b
b,c
c,i
i,a
Sliv 1
0
1
2
1
2
3
4
left 1
0
1
1
0
1
1
right 1
0
0
1
0
0
0
CDE
a,d d,a
c
g
b
i
a
left(f)
right(a)
Esempio:
f
d
lca(a,f)=c
a,i
i,g
g,i
i,c
c,f
f,c
c,h
3
2
3
2
1
2
1
0
1
0
0
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Discendenti di un nodo
Fatto: Sia dato un albero T con i nodi numerati in postorder. Il numero dei nodi nel
sottoalbero radicato in un nodo v (incluso) è dato dalla differenza tra il massimo ed il
minimo valore che i nodi in Tv hanno nella numerazione, ovvero è dato dalla differenza del
numero di nodi visitati prima di ritornare a p(v) e il numero di nodi visitati prima di
raggiungere v.
Con la numerazione in postorder il massimo valore in Tv è esattamente quello di Post(v)
mentre il minimo può essere trovato in corrispondenza dell’arco (p(v),v).
Il numero di discendenti della radice è
per ogni altro nodo il valore è
|Tr| = n
|Tv| = S(v,p(v)) - S(p(v),v)
CDE h e h c b c i a d a i g i c f c
0 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1
S 0 1 1 1 2 2 2 2 3 4 4 5 6 6 7 8
v a b c d e f g h i
|Tv| 2 1 7 1 1 1 1 9 4
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Ear Decomposition
Dato un grafo non orientato G e P0 ciclo semplice in G, una
Ear Decomposition è una partizione ordinata dell’insieme
degli archi E = P0P1P2…Pk tale che 1ik Pi è un
cammino semplice in cui entrambi gli estremi (e solo gli
estremi) appartengono a P0…Pi-1. Non è unica:
P3
P0
P2
P0
P1
P1
P2
P0
P3
Se 1ik Pi non è un ciclo (gli estremi sono distinti) allora
la decomposizione si dice aperta (vedi secondo esempio).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Quali grafi ammetto una Ear
Decomposition?
G è privo di ponti   EAR Decomposition
P0
P1
NO
SI
G è biconnesso   EAR Decomposition aperta
P2
P1
P3
P0
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Ear e Spanning Tree
Dato G si consideri un suo spanning tree T. Esistono m-n+1 archi di
G non in T, ciascuno dei quali induce un ciclo se viene aggiunto a
T.
3
e1
e2
3
2
e7
e8
1
4
e9
5
e3
2
6
4
e6
e4
8
e10
9
1
5
8
7
e5
6
9
7
Questa è una copertura del grafo tramite cicli, non una Ear
Decomposition: infatti due cicli possono condividere degli archi.
È necessario “rompere” i cicli per ottenere una Ear Decomposition.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
Etichettare gli archi
Etichettiamo ogni arco e=(u,v) in G-T nel seguente modo:
label(e) = <level(lca(u,v)),e>
Livello e lca sono da intendersi in T, aggiungiamo l’indice
dell’arco per disambiguare ed avere tutte etichette distinte.
Poi etichettiamo gli archi in T assegnando a ciascun arco
e=(u,v) in T la minima etichetta associata ad una arco e' non
in T che induce un ciclo contente e.
eT label(e)
eT
(2,1)
(1,8)
(3,5)
(7,8)
(7,6)
lca
3
4
3
8
4
label(e)
<0,e8>
<1,e9>
<0,e2>
<2,e10>
<1,e4>
(3,2)
(3,4)
(4,1)
(4,8)
(4,5)
(8,9)
(9,7)
(5,6)
Algoritmi Paralleli e Distribuiti a.a. 2008/09
<0,e8>
<0,e2>
<0,e8>
<1,e4>
<0,e2>
<1,e4>
<1,e4>
<1,e4>
10
Risultato
Ordinando gli archi rispetto a label(e) si ottiene la Ear
Decomposition come sequenza ordinata di cammini disgiunti.
e
(4,5)
(3,5)
(3,4)
(4,1)
(3,2)
(2,1)
(8,9)
(5,6)
(9,7)
(7,6)
(4,8)
(1,8)
(7,8)
label(e)
<0,e2>
<0,e2>
<0,e2>
<0,e8>
<0,e8>
<0,e8>
<1,e4>
<1,e4>
<1,e4>
<1,e4>
<1,e4>
<1,e9>
<2,e10>
3
Pe2
Pe8
Pe8
Pe2
2
4
1
Pe9
5
8
6
Pe4
Pe10
Pe9
9
Pe4
7
Pe10
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11