Il Problema dell’MST: esempio, 1
Si applichi l’algoritmo di Kruskal per individuare un MST
per il grafo riportato in Figura (a).
Inizialmente si hanno 5 componenti connesse, una per ogni nodo, come mostrato in Figura (b).
a) un semplice grafo non orientato avente 5 nodi ed 8 archi; b) foresta costituita dalle 5 componenti connesse costruite in fase d'inizializzazione. Disegnata da Paola Festa
Il Problema dell’MST: esempio, 1
Gli archi vengono ordinati e memorizzati per valore non decrescente dei costi, come in Tabella.
Dunque, L={[1,2],[2,3],[4,5],[1,3],[2,4],[3,5],[2,5],[1,4]}.
Tabella Archi e costi. Disegnata da Paola Festa
Il Problema dell’MST: esempio, 2
I iterazione: viene considerato l’arco [1,2]=L[1].
C[1]=1, C[2]=2, k=1.
Dal momento che C[1] è diverso da C[2], l’arco [1,2] può essere incluso nell’MST in costruzione.
Così, E’={[1,2]} e W=1.
Rimane da effettuare l’unione delle componenti C[1] e C[2].
Per fare ciò, occorre porre C[2]=C[1]=1, ottenendo la foresta riportata in Figura (a).
a) foresta costituita dalle 4 componenti connesse ottenuta alla fine della I iterazione; b) foresta costituita dalle 3 componenti connesse ottenuta alla fine della II iterazione. Disegnata da Paola Festa
Il Problema dell’MST: esempio, 3
II iterazione: k=2.
Viene considerato l’arco [2,3]=L[2].
C[2]=1, C[3]=3.
Dal momento che C[2] è diverso da C[3], l’arco [2,3] può essere incluso nell’MST in costruzione.
Così, E’={[1,2],[2,3]} e W=1+1=2.
Occorre ora unire le componenti C[1] (C[2]=C[1]) e C[3]. Per fare ciò, occorre porre C[3]=C[1]=1, ottenendo la foresta riportata in Figura (b).
a) foresta costituita dalle 4 componenti connesse ottenuta alla fine della I iterazione; b) foresta costituita dalle 3 componenti connesse ottenuta alla fine della II iterazione. Disegnata da Paola Festa
Il Problema dell’MST: esempio, 4
III iterazione: k=3.
Viene considerato l’arco [4,5]=L[3].
C[4]=4, C[5]=5.
Dal momento che C[4] è diverso da C[5], l’arco [4,5] può essere incluso nell’MST in costruzione.
Così, E’={[1,2],[2,3],[4,5]} e W=2+1=3.
Occorre, ora, unire le componenti C[4] e C[5].
Per fare ciò, occorre porre C[4]=C[5]=4, ottenendo la foresta riportata in Figura (a).
a) Foresta costituita dalle 2 componenti connesse ottenuta alla fine della III iterazione; b) Minimum Spanning Tree per G. Disegnata da Paola Festa
Il Problema dell’MST: esempio, 5
IV iterazione: k=4.
Viene considerato l’arco [1,3]=L[4].
C[4]=4, C[5]=5.
Dal momento che C[1]=C[3]=1, l’arco [1,3] non può essere incluso nell’MST in costruzione.
Infatti, se [1,3] fosse selezionato, nella componente costituita dai nodi 1, 2 e 3 (vedi Figura (a)) si formerebbe il ciclo C={[1,2],[2,3],[3,1]}.
a) Foresta costituita dalle 2 componenti connesse ottenuta alla fine della III iterazione; b) Minimum Spanning Tree per G. Disegnata da Paola Festa
Il Problema dell’MST: esempio, 6
V iterazione: k=4.
Viene considerato l’arco [2,4]=L[5].
C[2]=1, C[4]=4.
Dal momento che C[2] è diverso da C[4], l’arco [2,4] può essere incluso nell’MST in costruzione.
Così, E’={[1,2],[2,3],[4,5],[2,4]} e W=3+3=6.
Occorre, ora, unire le componenti C[2] e C[4].
Per fare ciò, occorre porre C[4]=C[2]=1, ottenendo il Minimum Spanning Tree mostrato in Figura (b).
Nota: Al termine dell’algoritmo k=4=n-1.
a) Foresta costituita dalle 2 componenti connesse ottenuta alla fine della III iterazione; b) Minimum Spanning Tree per G. Disegnato da Paola Festa
Il Problema dell’MST: esercizio
Esercizio
Si applichi l’algoritmo di Kruskal per individuare un MST per il grafo riportato in Figura.
Un semplice grafo non orientato avente 9 nodi. Disegnato da Paola Festa
Le lezioni del Corso
1. Presentazione del Corso ed Introduzione alla Programmazione Mat...
2. Introduzione ai Problemi di PL
6. Algoritmo del Simplesso Revisionato
7. Algoritmo del Simplesso Tabellare
10. Soluzione di Problemi di PL tramite Algoritmo del Simplesso
11. Problemi di Programmazione Lineare Intera
12. PLI con matrice dei vincoli unimodulare
13. Problemi di PLI: Branch & Bound
14. Il Problema dello Zaino 0/1 e il Problema dello Zaino Frazionar...
15. Il Problema dello Zaino 0/1: un algoritmo B&B
16. Il Problema dello Zaino 0/1: un algoritmo di Programmazione Din...
17. Richiami di Teoria dei Grafi: definizioni e notazioni
18. Il Problema del Vertex Cover Minimo di un Grafo
19. Il Problema dell'Albero di Copertura Minimo (MST)
20. Il Problema dell'Albero di Copertura Minimo (MST): esempio
I materiali di supporto della lezione
D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.
M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.
S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.
S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.
Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.
Dispense ed Appunti del Corso prodotte da Paola Festa.
