Post on 15-Aug-2020
18
Minimo sottografo ricoprente
Dato un grafo connesso G = (V, E) con costi positivi sugli archi ce, un minimo
sottografo ricoprente è un insieme di archi E’ ⊆ E tale che:
・ G’ = (V, E’) è connesso
・c(E’) = ∑e ce ≤ c(F) per ogni altro insieme di archi F ⊆ E tale che H = (V, F) è connesso.
16
4
6 23
10
21
14
24
189
7
115
8
19
Minimo sottografo ricoprente
Dato un grafo connesso G = (V, E) con costi positivi sugli archi ce, un minimo
sottografo ricoprente è un insieme di archi E’ ⊆ E tale che:
・ G’ = (V, E’) è connesso
・c(E’) = ∑e ce ≤ c(F) per ogni altro insieme di archi F ⊆ E tale che H = (V, F) è connesso.
16
4
6 23
10
21
14
24
189
7
115
8
Osservazione: G’ = (V, E’) non contiene cicli, quindi è un albero
20
Minimo albero ricoprente
Dato un grafo connesso G = (V, E) con costi positivi sugli archi ce, un minimo
albero ricoprente è un insieme di archi E’ ⊆ E tale che:
・ G’ = (V, E’) è un albero
・c(E’) = ∑e ce ≤ c(F) per ogni altro insieme di archi F ⊆ E tale che H = (V, F) è un albero.
16
4
6 23
10
21
14
24
189
7
115
8
Osservazione: G’ = (V, E’) non contiene cicli, quindi è un albero
MST di costo = 50 = 4 + 6 + 8 + 5 + 11 + 9 + 7
21
Minimo albero ricoprente
Dato un grafo connesso G = (V, E) con costi positivi sugli archi ce, un minimo
albero ricoprente è un insieme di archi E’ ⊆ E tale che:
・ G’ = (V, E’) è un albero
・c(E’) = ∑e ce ≤ c(F) per ogni altro insieme di archi F ⊆ E tale che H = (V, F) è un albero.
16
4
6 23
10
21
14
24
189
7
115
8
Teorema[Cayley]. Un grafo può avere fino a nn–2 alberi ricoprenti
MST di costo = 50 = 4 + 6 + 8 + 5 + 11 + 9 + 7 non possiamo cercarlo esaustivamente
22
Applicazioni
MST è un problema che si ritrova in numerose applicazioni.
・design di reti (telefoniche, idrauliche, stradali)
・clustering.
・compressione dati in proteomica.
・generazione di ipotesi evolutive.
MST su 59 aplotipi di Salmonella Typhi
la lunghezza degli archi rappresenta la
differenza in numero di SNP
23
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
24
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 25
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
26
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 27
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
28
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 29
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
30
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 31
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
32
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 33
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
34
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 35
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
36
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 37
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
38
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 39
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal
40
Algoritmi greedi per MST
Diverse tecniche greedy forniscono una soluzione ottima.
Algoritmo di Prim.
・comincia con un singolo nodo arbitrario s: T = {s}
・aggiungi l’arco di costo minimo con una sola terminazione in T
Algoritmo di Kruskal
・comincia con T = ��・considera gli archi in ordine crescente di costo, aggiungi un arco a T se
non crea un ciclo
16
4
6 23
10
21
14
24
189
7
115
8
16
4
6 23
10
21
14
24
189
7
115
8
Prim Kruskal 41
Osservazioni
Cicli.
・Aggiungendo un arco e ad un albero (ricoprente) T crea un ciclo C.
・Eliminando un arco f ∈ C da T ∪ { e } otteniamo un nuovo albero
ricoprente.
Osservazione. Se ce < cf, allora T NON è un MST.
T = (V, F)
e
f
42
Ottimalità dell’algoritmo di Prim
Teorema. L’algoritmo di Prim produce un MST
Dim
・sia f il primo arco scelto da Prim che non è in un MST
・S è il sottoalbero costruito da Prim che è parte di un MST
・gli archi verdi sono la restante parte di un tale MST T
・se aggiungiamo f creiamo un ciclo
・cf < ce (perché scelto da Prim) quindi T - e ∪ f ha costo inferiore a T
S
e
f
43
Algoritmo di Prim: implementazione
L’algoritmo di Prim può essere implementato in tempo O(m log n).
・quasi identica a quella dell’algoritmo di Dijkstra.
[ d(v) = minimo costo di un arco tra v e S ]
PRIM (V, E, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Crea una coda a priorità S.
s ← un qualsiasi nodo di V.
FOR EACH v ≠ s : d(v) ← ∞; d(s) ← 0.
FOR EACH v : Insert (S, v, d(v)).
WHILE (S is not empty)
(u, d[u]) ← Extract-min(S).
FOR EACH arco (u, v) ∈ Adj[u]:
IF d(v) > c(u, v)
Decrease-val(S, v, c(u, v)).
d(v) ← c(u, v)._________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
44
Algoritmo di Prim - esempio
1 6
4
7 3
9
2
10
11
58 12
13
45
Algoritmo di Prim - esempio
3 11
5
0
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
46
Algoritmo di Prim - esempio
3 11
5
5
3 110
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
47
Algoritmo di Prim - esempio
3
5
113 0
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
48
Algoritmo di Prim - esempio
3
5
11
7
8 12
3 0
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
49
Algoritmo di Prim - esempio
3
5
11
7
8
3 0
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
50
Algoritmo di Prim - esempio
3
5
11
7
8
3
8
7 0
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
51
Algoritmo di Prim - esempio
3
5
113
8
7 0
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
52
Algoritmo di Prim - esempio
3
5
113 0
5
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
53
Algoritmo di Prim - esempio
3
5
113 0
13 2
105
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
54
Algoritmo di Prim - esempio
3
5
113 0
2
105
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
55
Algoritmo di Prim - esempio
3
5
103 0
2
5
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
56
Algoritmo di Prim - esempio
3
5
103 0
2
5
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
57
Algoritmo di Prim - esempio
3
5
103 0
2
5
2
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
58
Algoritmo di Prim - esempio
3
5
103 0
2
5
2
9
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
59
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
8
7
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
60
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
8
77
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
61
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
8
77
1 6
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
62
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
6
77
1
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
63
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
6
77
1
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
64
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
6
77
1
1
4
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
65
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
4
77
1
1
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
66
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
4
77
1
1
4
Comincia con S = un nodo qualsiasi.
Ripeti n – 1 volte:
・Aggiugi all’albero l’arco di minimo costo con un solo vertice in S.
・Aggiungi il nuovo nodo ad S.
67
Algoritmo di Prim - esempio
3
5
93 0
2
5
2
4
77
1
1
4
9
68
Algoritmo di Prim: implementazione
L’algoritmo di Prim può essere implementato in tempo O(m log n).
・quasi identica a quella dell’algoritmo di Dijkstra.
[ d(v) = minimo costo di un arco tra v e S ]
PRIM (V, E, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Crea una coda a priorità S.
s ← un qualsiasi nodo di V.
FOR EACH v ≠ s : d(v) ← ∞; d(s) ← 0.
FOR EACH v : Insert (S, v, d(v)).
WHILE (S is not empty)
(u, d[u]) ← Extract-min(S).
FOR EACH arco (u, v) ∈ Adj[u]:
IF d(v) > c(u, v)
Decrease-val(S, v, c(u, v)).
d(v) ← c(u, v)._________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Running time
T(n) = O(m log n)∑u degree(u) = 2m