Mathematical Engineering - Fondamenti di Ricerca Operativa

Grafi

Divided by topic

Fondamenti di Ricerca OperativaEsercizi proposti Problemi su grafi AA. 2019/2020 Fondamenti di Ricerca Operativapagina 1 Esercizio 1Si consideri il problema di flusso massimo (Figura 1) dal nodo 1 al nodo 6, dove per ciascun arco sono indicati il flusso dato e la capacit`a, in quest’ordine (x ij, u ij). •Trovare la soluzione ottima a partire dal flusso dato, riportando i grafi residuali. •Trovare un taglio di capacit`a minima, illustrando i passi della procedura 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 2Calcolare l’albero di copertura di costo minimo sul grafo in Figura 2, illustrando 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 grafiGiuliana Carello Fondamenti di Ricerca Operativapagina 2 Esercizio 3Si consideri il grafo riportato in Figura 3, dove `e indicato il costo associato 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 nel nodo 1, illustrando i passi dell’algoritmo applicato. Esercizio 4Si consideri il seguente problema di flusso massimo dal nodo 1 al nodo 7, dove per ciascun arco sono indicati il flusso dato e la capacit`a, in quest’ordine (x ij, u ij). •Trovare la soluzione ottima a partire dal flusso dato, riportando i grafi incrementali. •Trovare un taglio di capacit`a minima, illustrando i passi della procedura 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 grafiGiuliana Carello Fondamenti di Ricerca Operativapagina 3 Esercizio 5Trovare 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 6Trovare l’albero di copertura di costo minimo sul seguente grafo,indicando i passi dell’algoritmo applicato: 1 2 3 4 5 6 7 8 9 7 6 1 1 2 4 3 3 5 Esercizio 7Trovare l’albero di cammini minimi con radice 1 sul seguente grafo: 1 2 3 4 6 5 7 11 19 8 10 6 19 19 15 6 3 19 Problemi su grafiGiuliana Carello Fondamenti di Ricerca Operativapagina 4 Esercizio 8Determinare l’albero di copertura di costo minimo per il seguente grafo. Variante:Un nodo, con indice 10, ed i lati{3,10},{5,10}e{9,10}con costo 3,4,5 sono aggiunti al grafo. Come cambia la soluzione ottima? Come pu`o essere calcolata senza dover ri-eseguire l’algoritmo dall’inizio? Problemi su grafiGiuliana Carello