Testo del “Compito a casa n. 2”
Esercizio 1
Dato il grafo G = (V, E) determinare il taglio di capacità minima, evidenziando i passi elementari dell’algoritmo utilizzato.
22 15
12 30 14 23
9 20
17
19 11 12
18 75
25 Esercizio 2
Data la matrice di figura, arrotondare ciascuno dei suoi elementi all’intero superiore o inferiore in modo tale che la somma degli elementi sulle righe e la somma degli elementi sulle colonne sia pari all’arrotondamento (all’intero inferiore o superiore) delle somme degli elementi originari della matrice.
12.4 16.2 13.7 11.9 8.7 62.9 11.4 12.4 8.2 10.8 9.9 52.7 9.3 8.6 7.4 10.4 10.8 46.5 8.7 9.4 19.2 17.2 12.9 67.4 9.8 14.2 11.1 12.2 15.7 63 17.2 18.2 21.2 7.4 14.3 78.3
68.8 79 80.8 69.9 72.3
♣
Esercizio 3
Dato il grafo G = (V, E) di figura, individuare il numero minimo di spigoli la cui rimozione determina un grafo sconnesso.
♣