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).
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]}.
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).
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).
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).
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]}.
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.
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
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.