Mauro Passacantando Dipartimento di Informatica Largo B. Pontecorvo 3, Pisa [email protected]
Definizioni
Albero
In un grafo (N, A) non orientato e connesso, unalbero`e un insieme di archi connesso e privo di cicli.
Albero di copertura
In un grafo (N, A) non orientato e connesso, unalbero di copertura`e un albero che connette tutti i nodi del grafo.
Esercizio
Quanti archi ha un albero di copertura? Perch´e?
Problema
Dato un grafo (N, A) non orientato e connesso, trovare un albero di copertura di costo minimo.
Algoritmo di Kruskal
1. Disponi gli archi a1, . . . , am in ordine crescente di costo. T := ∅, j := 1.
2. se T ∪ {aj} non contiene un ciclo allora inserisci aj in T 3. se |T | = n − 1 allora STOP
altrimenti j := j + 1 e torna al passo 2
vedi anche:
http://www.cut-the-knot.org/Curriculum/Combinatorics/MinimumSpanningTree.shtml
Correttezza dell’algoritmo di Kruskal
Teorema
L’algoritmo di Kruskal trova un albero di copertura di costo minimo.
Dimostrazione
T `e un albero (perch´e non contiene cicli) di copertura (perch´e ha n − 1 archi).
Per dimostrare che T `e ottimo, dimostriamo che per ogni k = 0, . . . , n − 1 vale questa propriet`a:
durante l’esecuzione dell’algoritmo, se T ha k archi
allora esiste un albero ottimo T′ che contiene T . (P) Dimostrazione per induzione su k.
Per k = 0 (P) `e ovviamente vera.
Supponiamo che (P) sia vera per un certo k < n − 1 e dimostriamo che (P) `e vera anche per k + 1.
Supponiamo che il prossimo arco che viene inserito in T sia {i, j}.
Se {i, j} ∈ T′, allora T′ contiene T ∪ {i, j}, quindi (P) `e vera anche per k + 1.
Dimostrazione (segue)
Se {i, j} /∈ T′, allora T′∪ {i, j} contiene un ciclo C . In C esiste un arco {p, q} /∈ T . Dimostriamo ora che cpq≥ cij. Infatti, se cpq< cij e {i, j} `e il prossimo arco che viene inserito in T , allora l’arco {p, q} dovrebbe formare un ciclo con gli archi di T , ma T ⊂ T′e quindi {p, q} ∈ T′ formerebbe un ciclo con gli archi di T′, che `e impossibile perch´e T′`e un albero.
L’insieme T′′= T′\ {p, q} ∪ {i, j} `e un albero di copertura e costo(T′′) = costo(T′) − cpq+ cij ≤ costo(T′), quindi T′′`e ottimo e contiene T ∪ {i, j}, quindi (P) `e vera anche per k + 1.
q j
p i
T′
C
q j
p i
T′′
Implementazione dell’algoritmo di Kruskal
Per controllare l’esistenza di un ciclo usiamo delle etichette d sui nodi in modo che:
• i nodi di una componente connessa di T abbiano la stessa etichetta
• i nodi di due componenti connesse diverse di T abbiano etichette diverse Algoritmo di Kruskal
1. Disponi gli archi a1, . . . , am in ordine crescente di costo.
T := ∅, j := 1, di := i per ogni i = 1, . . . , n 2. Sia aj = {p, q} con dp ≤ dq.
se dp< dq allora T := T ∪ {aj}
per ogni i = 1, . . . , n: se di= dq allora di := dp
3. se |T | = n − 1 allora STOP
altrimenti j := j + 1 e torna al passo 2
1
2
3
4 5
6
3 6
9
4
3 1
1 8
2 7
{1, 2} {1, 3} {1, 6} {2, 3} {2, 4} {3, 4} {3, 5} {3, 6} {4, 5} {5, 6}
3 6 9 4 3 1 1 8 2 7
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
2
3
4 5
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
2
3
4 5
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
2
3
3 5
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
2
3
3 5
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
2
3
3 3
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
2
3
3 3
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
2
3
3 3
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
2
3
3 3
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
1
3
3 3
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
1
3
3 3
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
1
1
1 1
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
1
1
1 1
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
1
1
1 1
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
1
1
1 1
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
1
1
1 1
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
1
2
3
4 5
6
1
1
1
1 1
6
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Algoritmo di Kruskal: esempio
1
2
3
4 5
6
1
1
1
1 1
1
{3, 4} {3, 5} {4, 5} {1, 2} {2, 4} {2, 3} {1, 3} {5, 6} {3, 6} {1, 6}
1 1 2 3 3 4 6 7 8 9
Soluzione alternativa: costruisco l’albero mantenendo una sola componente connessa C . Ad ogni iterazione aggiungo l’arco di costo minimo che collega C ai nodi non ancora connessi.
1. Scegli un nodo k. Poni C = {k} e T = ∅.
2. se C = N allora STOP 3. Calcola
i ∈C, j /min∈Ccij= cpq,
inserisci l’arco (p, q) in T , inserisci il nodo q in C e torna al passo 2.
Implementazione dell’algoritmo di Prim
Per trovare il prossimo nodo da aggiungere a C e il prossimo arco da aggiungere a T, utilizzo per ogni nodo i due etichette di e pi:
- di `e il minimo costo per collegare i a C
- pi `e il predecessore di i, serve per memorizzare qual `e il modo migliore per collegare i a C .
1. Scegli un nodo k. Poni C = {k}, T = ∅, dk = 0, di = ∞ per ogni i 6= k, pi= −1 per ogni i.
2. se C = N allora STOP
3. Chiama u l’ultimo nodo inserito in C . Per ogni arco (u, j) con j /∈ C : se dj > cuj allora poni dj := cuj e pj = u
4. Calcola
minj∈/Cdj = dq,
inserisci il nodo q in C, inserisci l’arco (pq, q) in T e torna al passo 2.
vedi anche:
