1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Enumerazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Tempo di esecuzione degli algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Problemi di ottimizzazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Ordinamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Definizioni fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Alberi, cicuiti, e tagli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Connettività . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Grafi di Eulero e grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5 Planarità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.6 Dualità Planare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.1 Poliedri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 Algoritmo del simplesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3 Implementazione dell’algoritmo del simplesso . . . . . . . . . . . . . . . . . 63
3.4 Dualità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5 Inviluppi convessi and politopi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4 Algoritmi di programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.1 Dimensione dei vertici e delle facce . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2 Frazioni continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3 Eliminazione di Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 Il metodo dell’elissoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.5 Il Teorema di Khachiyan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.6 Separazione ed ottimizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5 Programmazione intera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.1 Inviluppo convesso di un poliedro . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.2 Trasformazioni unimodulari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.3 Integralità totalmente duale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.4 Matrici totalmente unimodulari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.5 Piani di taglio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.6 Rilassamento lagrangiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6 Alberi di supporto e arborescenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.1 Alberi di supporto minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2 Arborescenze di peso minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.3 Descrizioni poliedrali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4 Packing alberi di supporto e arborescenze . . . . . . . . . . . . . . . . . . . . 149
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7 Cammini minimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.1 Cammini minimi da una singola sorgente . . . . . . . . . . . . . . . . . . . . . 160
7.2 Cammini minimi tra tutte le coppie di vertici . . . . . . . . . . . . . . . . . 164
7.3 Circuiti di peso medio minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8 Reti di flusso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.1 Il Teorema di massimo flusso–minimo taglio . . . . . . . . . . . . . . . . . . 174
8.2 Teorema di Menger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.3 Algoritmo di Edmonds-Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.4 Flussi bloccanti e il teorema di Fujishige . . . . . . . . . . . . . . . . . . . . . . 182
8.5 L’algoritmo di Goldberg-Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
8.6 Alberi di Gomory-Hu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.7 Taglio di capacità minima in grafo non-orientato . . . . . . . . . . . . . . 195
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
9 Flussi di costo minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.1 Formulazione del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.2 Un criterio di ottimalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
9.3 Algoritmo di cancellazione di cicli di peso medio minimo . . . . . . 211
9.4 Algoritmo di Ford-Fulkerson scmcfpath . . . . . . . . . . . . . . . . . . . . . . . 215
9.5 Algortimo di Orlin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
9.6 Algoritmo del simplesso per le reti di flusso sc
