Rete di flusso 1

Page 1

Esercitazione MORO - 21 Dicembre 2016 Esercizio 1. Un insieme di nodi N di una rete di telecomunicazione deve essere collegato tram ite tratte. `E possibile attivare una tratta { i, j}, con i < j , che appartiene ad un insieme di tratte disponibili, ad un costo cij > 0. Ogni tratta installata pu` o essere usata in entrambe le di rezioni. I nodi da collegare, le tratte disponibili e il loro costo sono rappresentate nella figura. Si vuole decidere la topologia, ovvero quali tratte siano attivate, della rete di costo minimo che garantisca la connessione di tutti i nodi in N . Risolvere il problema descritto con un algoritmo per proble mi su grafi noto. 1 2 4 3 5 6 7 8 7 5 6 4 3 2 1 1 5 2 2 T raccia di soluzione. Il problema richiede di trovare l’albero di copertura di cos to minimo e pu` o essere risolto con gli algoritmi di Kruskal e Prim. Algoritmo di Kruskal sequenza arco valore inserito 1 (3,4) 1 SI 2 (3,5) 1 SI 3 (2,7) 2 SI 4 (4,5) 2 chiude circuito 5 (5,6) 2 SI 6 (2,4) 3 SI 7 (2,3) 4 chiude circuito 8 (1,6) 5 SI: STOP 9 (3,6) 5 10 (1,7) 6 11 (1,3) 7 12 (1,2) 8 1 1 2 4 3 5 6 7 1 1 2 2 3 5 Figura 1: Albero ottenuto con l’algoritmo di Kruskal, costo 14 Algoritmo di Prim Selezioniamo il nodo 1 sequenza arco valore 1 (1,6) 5 2 (5,6) 2 3 (3,5) 1 4 (3,4) 1 5 (3,4) 3 6 (2,7) 2 1 2 4 3 5 6 7 5 2 1 1 3 2 Figura 2: Albero ottenuto con l’algoritmo di Prim, costo 14 ♦ 2 Esercizio 2. Dato il grafo in figura trovare l’albero di copertura di costo minimo, applicando gli algoritmi di Kruskal e Prim. 1 2 4 3 5 6 4 2 3 6 7 4 5 7 4 6 T raccia di soluzione. Algoritmo di Kruskal sequenza arco valore inserito 1 (1,4) 2 SI 2 (1,5) 3 SI 3 (1,2) 4 SI 4 (4,2) 4 chiude circuito 5 (4,5) 4 chiude circuito 6 (2,5) 5 chiude circuito 7 (1,3) 6 SI 8 (5,6) 6 SI: STOP 9 (2,3) 7 10 (2,6) 7 3 1 2 4 3 5 6 4…