Diszkrét optimalizálás

Bevezetés......Page 9
Legolcsóbb feszítő fák......Page 10
Láncok, utak, részfák......Page 13
Irányítások......Page 15
Színezések......Page 18
Forrás telepítés......Page 19
Kőnig és Hall tételei......Page 20
Fokszámkorlátos irányítások......Page 22
Algoritmikus bizonyítások III: helyi javítások......Page 27
Irányítások......Page 28
Párosítások......Page 29
A szintező algoritmus megengedett m-áramok kiszámítására......Page 30
Szétszedés pontos halmaz mentén......Page 36
Elemi konstrukciók......Page 42
Pontszétnyitás......Page 43
Hall tétele újra......Page 46
Él-Menger újra......Page 48
Irányítási lemma újra......Page 49
Megengedett áramok: Hoffman tétele......Page 50
Minimális költségű fenyők......Page 51
Fenyők és fák pakolása......Page 57
Fedés fenyvesekkel és erdőkkel......Page 61
Maximális párosítások......Page 62
Perfekt gráfok......Page 68
Bevezetés......Page 73
Függetlenségi axiómák......Page 75
Példák matroidokra......Page 78
További fogalmak......Page 79
Körök tulajdonságai, köraxiómák......Page 81
Felbonthatóság......Page 84
Bázisaxiómák......Page 88
Rangaxiómák......Page 91
Orákulumok......Page 93
A mohó algoritmus......Page 95
Matroidok poliéderei......Page 99
Elemi műveletek......Page 102
Duális matroid......Page 104
Minorok: elhagyás és összehúzás......Page 108
Maximális súlyú bázisok matroidja......Page 109
Matroidok halmazrendszerekből és gráfokból......Page 110
Partíciós matroid és rokonai......Page 111
Transzverzális matroidok és deltoidok......Page 113
Párosítás-matroid......Page 115
Gammoidok......Page 116
Matroidok összege......Page 117
A matroidmetszet-tétel......Page 120
Oldalak......Page 125
Egész megoldások......Page 127
Teljesen duálisan egészértékű rendszerek......Page 128
TU-mátrixok: példák, alaptulajdonságok......Page 129
Lamináris hipergráfok......Page 133
Keresztezésmentes hipergráfok......Page 135
Farkas-lemma, dualitás, optimalitási feltételek TU-mátrixokra......Page 136
Kerekítés......Page 139
Egyenletes színezések......Page 140
TU-mátrixok jellemzése......Page 141
Páros gráfok: optimális részgráfok......Page 143
Páros gráfok: élszínezések......Page 146
Megengedett potenciálok, legolcsóbb utak......Page 148
Megengedett áramok és folyamok......Page 149
Minimális költségű áramok és folyamok......Page 150
Hálózati mátrixokkal adott lineáris programok......Page 154
Az irányított kínai postás probléma......Page 155
Aciklikus digráfok optimális fedése utakkal......Page 157
Fedés körökkel......Page 160
Gyökeresen k-élösszefüggő digráfok......Page 163
Merev és infinitezimálisan merev szerkezetek......Page 167
Merev gráfok a síkban......Page 171
A merevség tesztelése......Page 178
Rögzítés pontleszúrással......Page 180
Összefüggőség és merevség......Page 182
Fogalmak, jelölések......Page 185
Egyszerűbb tulajdonságok......Page 189
NP-teljes problémák......Page 191