47,40 €*
Versandkostenfrei per Post / DHL
Lieferzeit 4-7 Werktage
risultati teorici e gli algoritmi che, al contrario delle euristiche, hanno una garanzia
di avere buone prestazioni. Comprende una vasta scelta di argomenti e nasce
come riferimento di diversi corsi di ottimizzazione combinatoria sia di base che di
livello avanzato. Il libro contiene dimostrazioni complete (ma concise) anche
di molti risultati avanzati, alcuni dei quali non sono mai apparsi prima in un libro.
Vengono anche trattati molti dei temi di ricerca più attuali e sono riportati molti
riferimenti alla letteratura. Quindi questo libro, traduzione della quarta edizione in lingua originale, rappresenta lo stato dell¿arte dell¿ottimizzazione combinatoria.
risultati teorici e gli algoritmi che, al contrario delle euristiche, hanno una garanzia
di avere buone prestazioni. Comprende una vasta scelta di argomenti e nasce
come riferimento di diversi corsi di ottimizzazione combinatoria sia di base che di
livello avanzato. Il libro contiene dimostrazioni complete (ma concise) anche
di molti risultati avanzati, alcuni dei quali non sono mai apparsi prima in un libro.
Vengono anche trattati molti dei temi di ricerca più attuali e sono riportati molti
riferimenti alla letteratura. Quindi questo libro, traduzione della quarta edizione in lingua originale, rappresenta lo stato dell¿arte dell¿ottimizzazione combinatoria.
Traduzione di un famoso testo pubblicato in diverse lingue dalla casa madre
Punto di riferimento insostituibile per ricercatori e studeni del settore
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 flussö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 scnetworksimplex . . . 223
9.7 Flussi temporali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
10 Accoppiamenti di peso massimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10.1 Accoppiamento bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10.2 La matrice di Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
10.3 Il teorema di Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
10.4 Ear-Decomposizione di grafi Factor-Critical . . . . . . . . . . . . . . . . . . . 243
10.5 Algoritmo di accopiamento di Edmonds . . . . . . . . . . . . . . . . . . . . . . . 249
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
11 Matching Pesato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
11.1 Il problema di assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
11.2 Schema dell¿algoritmo di accoppiamento di peso massimo . . . . . . 267
11.3 Implementazione dell¿algoritmo di matching pesato massimo . . . . 270
11.4 Postottimalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
11.5 Il politopo di matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Riferimenti bibliografici . . . . . . ....
Erscheinungsjahr: | 2011 |
---|---|
Fachbereich: | Wahrscheinlichkeitstheorie |
Genre: | Mathematik |
Rubrik: | Naturwissenschaften & Technik |
Medium: | Taschenbuch |
Seiten: | 696 |
Reihe: | La Matematica per il 3+2 |
ISBN-13: | 9788847015227 |
ISBN-10: | 8847015227 |
Sprache: | Italienisch |
Herstellernummer: | 12752874 |
Ausstattung / Beilage: | Paperback |
Einband: | Kartoniert / Broschiert |
Autor: |
Vygen, Jens
Korte, Bernhard |
Auflage: | 2011 |
Hersteller: |
Springer Milan
Springer Italia S.r.l. La Matematica per il 3+2 |
Maße: | 235 x 155 x 38 mm |
Von/Mit: | Jens Vygen (u. a.) |
Erscheinungsdatum: | 04.01.2011 |
Gewicht: | 1,036 kg |
Traduzione di un famoso testo pubblicato in diverse lingue dalla casa madre
Punto di riferimento insostituibile per ricercatori e studeni del settore
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 flussö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 scnetworksimplex . . . 223
9.7 Flussi temporali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
10 Accoppiamenti di peso massimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10.1 Accoppiamento bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10.2 La matrice di Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
10.3 Il teorema di Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
10.4 Ear-Decomposizione di grafi Factor-Critical . . . . . . . . . . . . . . . . . . . 243
10.5 Algoritmo di accopiamento di Edmonds . . . . . . . . . . . . . . . . . . . . . . . 249
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
11 Matching Pesato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
11.1 Il problema di assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
11.2 Schema dell¿algoritmo di accoppiamento di peso massimo . . . . . . 267
11.3 Implementazione dell¿algoritmo di matching pesato massimo . . . . 270
11.4 Postottimalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
11.5 Il politopo di matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Riferimenti bibliografici . . . . . . ....
Erscheinungsjahr: | 2011 |
---|---|
Fachbereich: | Wahrscheinlichkeitstheorie |
Genre: | Mathematik |
Rubrik: | Naturwissenschaften & Technik |
Medium: | Taschenbuch |
Seiten: | 696 |
Reihe: | La Matematica per il 3+2 |
ISBN-13: | 9788847015227 |
ISBN-10: | 8847015227 |
Sprache: | Italienisch |
Herstellernummer: | 12752874 |
Ausstattung / Beilage: | Paperback |
Einband: | Kartoniert / Broschiert |
Autor: |
Vygen, Jens
Korte, Bernhard |
Auflage: | 2011 |
Hersteller: |
Springer Milan
Springer Italia S.r.l. La Matematica per il 3+2 |
Maße: | 235 x 155 x 38 mm |
Von/Mit: | Jens Vygen (u. a.) |
Erscheinungsdatum: | 04.01.2011 |
Gewicht: | 1,036 kg |