Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 20.Il Problema dell'Albero di Copertura Minimo (MST): esempio


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

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

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

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

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

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

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

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

Un semplice grafo non orientato avente 9 nodi. Disegnato da Paola Festa


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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion