Rete di flusso 2

Page 1

Esercitazione MORO - 11 Gennaio 2016 Esercizio 1. Calcolare il cammino minimo tra tutte le coppie di nodi sul se guente grafo: 1 2 3 4 6 5 10 3 -2 3-2 -4 -3 -5 12 T raccia di soluzione. Applichiamo l’algoritmo di Floyd-Warshall. Inizializzazione: d0 ij = cij se l’arco esiste, ∞ altrimenti k = 0 1 2 3 4 5 6 1 ∞ 10 3 ∞ ∞ ∞ 2 ∞ ∞ ∞ − 2 3 ∞ 3 ∞ − 2 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ − 4 5 ∞ ∞ − 3 −5 ∞ ∞ 6 ∞ ∞ ∞ ∞ 12 ∞ Prima iterazione: d1 ij = min{ d0 ij, d0 i1 + d0 1j} k = 0 1 2 3 4 5 6 1 ∞ 10 3 ∞ ∞ ∞ 2 ∞ ∞ ∞ − 2 3 ∞ 3 ∞ − 2 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ − 4 5 ∞ ∞ − 3 −5 ∞ ∞ 6 ∞ ∞ ∞ ∞ 12 ∞ Seconda iterazione: d2 ij = min{ d1 ij, d1 i2 + d1 2j} k = 0 1 2 3 4 5 6 1 ∞ 10 3 8 13 ∞ 2 ∞ ∞ ∞ − 2 3 ∞ 3 ∞ − 2 ∞ −4 1 ∞ 4 ∞ ∞ ∞ ∞ ∞ − 4 5 ∞ ∞ − 3 −5 ∞ ∞ 6 ∞ ∞ ∞ ∞ 12 ∞ 1 Terza iterazione d3 ij = min{ d2 ij, d2 i3 + d2 3j} k = 0 1 2 3 4 5 6 1 ∞ 1 3 −1 4 ∞ 2 ∞ ∞ ∞ − 2 3 ∞ 3 ∞ − 2 ∞ − 4 1 ∞ 4 ∞ ∞ ∞ ∞ ∞ − 4 5 ∞ −5 −3 −7 −2 ∞ 6 ∞ ∞ ∞ ∞ 12 ∞ Poich´ ed3 55 ` e negativo, l’algoritmo termina per aver rilevato la prese nza di un ciclo negativo (2 − 5 − 3). ♦ Esercizio 2. Determinare il flusso ammissibile di valore massimo dal nodo 1 al nodo 7 nel seguente grafo, in cui sono indicati, per ogni arco, la quantit` a iniziale di prodotto che lo attraversa e la capacit` a. Illustrare i passi dell’algoritmo applicato e indicare un taglio di cap acit` a minima. 1 2 4 3 5 6 7 3,6 5,10 6,6 3,3 0,3 4,4 5,5 4,5 2,7 7,9 2,8 T raccia di soluzione. Primo grafo residuale: 1 2 4 3 5 6 7 3 35 5 6 3 3 4 5 1 4 5 2 2 7 6 2 1 2 4 3 5 6 7 3(3) 5(5) 0(6) 0(3) 3(0) 0(4) 0(5) 1(4) 5(2) 2(7) 6(2) Cammino aumentante 1 - 3- 4- 6 -7, δ = 4. Il flusso passa da 14 a 18. Nuovo flusso. 1 2 4 3 5 6 7 3,6 9,10 6,6 3,3 0,3 4,4 5,5 0,5 6,7 7,9 6,8 Nuovo grafo residuale: 2 1 2 4 3 5 6 7 3 31 9 6 3 3 4 5 5 1 6 2 7 2 6 1 2 4 3 5 6 7 3(3) 1(9) 0(6) 0(3) 3(0) 0(4)…