Grafi

Page 1

Fondamenti di Ricerca Operativa Esercizi proposti Problemi su grafi AA. 2019/2020 Fondamenti di Ricerca Operativa pagina 1 Esercizio 1 Si consideri il problema di flusso massimo (Figura 1) dal nodo 1 al no do 6, dove per ciascun arco sono indicati il flusso dato e la capacit` a, in quest’o rdine ( xij , uij). • Trovare la soluzione ottima a partire dal flusso dato, riportando i g rafi residuali. • Trovare un taglio di capacit` a minima, illustrando i passi della proced ura applicata per trovarlo. 1 2 3 4 5 6 6,10 5,5 4,4 3,5 0,8 6,16 0,4 5,5 5,7 2,9 Figura 1: Flusso massimo Esercizio 2 Calcolare l’albero di copertura di costo minimo sul grafo in Figura 2, illu strando i passi dell’algoritmo applicato. 1 2 5 3 4 6 7 7 7 9 5 3 3 5 4 8 1 9 10 Figura 2: Albero di copertura Problemi su grafi Giuliana Carello Fondamenti di Ricerca Operativa pagina 2 Esercizio 3 Si consideri il grafo riportato in Figura 3, dove ` e indicato il costo a ssociato ad ogni arco. 1 2 4 3 5 6 10 3 2 2 5 5 2 10 3 6 Figura 3: Albero dei cammini minimi Calcolare l’albero dei cammini minimi sul seguente grafo, con radice n el nodo 1, illustrando i passi dell’algoritmo applicato. Esercizio 4 Si consideri il seguente problema di flusso massimo dal nodo 1 al no do 7, dove per ciascun arco sono indicati il flusso dato e la capacit` a, in quest’ordin e ( xij, uij). • Trovare la soluzione ottima a partire dal flusso dato, riportando i g rafi incrementali. • Trovare un taglio di capacit` a minima, illustrando i passi della proced ura applicata per trovarlo. 1 2 3 4 5 6 7 9,9 6,13 1,13 9,9 1,1 5,6 1,9 0,6 14,14 0,14 1,11 Problemi su grafi Giuliana Carello Fondamenti di Ricerca Operativa pagina 3 Esercizio 5 Trovare l’albero dei cammini minimi con radice 1 sul seguente grafo: 1 2 3 4 6 5 10 3 -2 3-2 -4 -3 -5 12 Esercizio 6…