Kombinatorikus optimalizálás: hálózatok és matroidok

Szerző

Szerkesztő

Fordító

Grafikus

Lektor

'Eugene L. Lawler: Kombinatorikus optimalizálás: hálózatok és matroidok ' összes példány

Kiadó:	Műszaki Könyvkiadó
Kiadás helye:	Budapest
Kiadás éve:	1982
Kötés típusa:	Vászon
Oldalszám:	359 oldal
Sorozatcím:
Kötetszám:
Nyelv:	Magyar
Méret:	24 cm x 17 cm
ISBN:	963-10-4181-6
Megjegyzés:	Fekete-fehér ábrákkal illusztrálva. Tankönyvi száma: 60933.

Értesítőt kérek a kiadóról

A beállítást mentettük,
naponta értesítjük a beérkező friss
kiadványokról

Tartalom

Előszó
Bevezetés
Mi a kombinatorikus optimalizálás?	11
Néhány jellegzetes optimalizálási probléma	12
Mikor tekinthetünk egy problémát megoldottnak?	13
A polinomkorlátosság kritériuma	14
Néhány nem polinomkorlátosnak tűnő probléma	17
Megoldási módszerek	18
Matematikai bevezető
Matematikai előfeltételek	23
Halmazok és relációk	24
Gráfok és irányított gráfok	27
Részgráfok, klikkek, multigráfok	31
Gráfok összefüggősége	33
Irányított gráfok összefüggősége	34
Vágások és irányított vágások	38
Síkbeliség és dualitás	39
Euler- és Hamilton-gráfok	42
Lineáris programozási problémák	44
A szimplex módszer	48
Geometriai interpretáció	52
A dualitás elmélete	57
Legrövidebb utak
Bevezetés	63
Néhány probléma megfogalmazása	65
Bellman-egyenletek	68
Körmentes hálózatok	71
Pozitív élű hálózatok: Dijkstra módszere	73
Megoldás fokozatos közelítéssel: a Bellmann-Ford módszer	76
Javítások a hatékonyságban: Yen módosításai	78
A lineáris programozás szerinti értelmezés és a helyreigazítási eljárások	79
Legrövidebb utak az összes csúcspár között: mátrixszorzás	83
Floyd-Warshall-módszer	86
Negatív körök kijelzése	90
Hálózatok áthaladási idővel	91
A minimális költség-idő hányadosú kör problémája	94
Az M-edik legrövidebb út: a Dreyfuss-módszer	96
Az M-edik legrövidebb út ismételt csúcsok nélkül	98
Hálózati folyamok
Bevezetés	105
Maximális folyamok	106
A maximális folyamot meghatározó algoritmus	109
A maximális folyamot meghatározó algoritmus hatékonysága	112
A maximális folyam - minimális vágás tétel kombinatorikai következményei	115
A maximális folyam - minimális vágás tétel lineáris programozási interpretációja	117
Minimális költségű folyamok	122
Veszteséges - nyereséges hálózatok	126
Alsó korlátok és cirkulációk	130
A kiltermódszer	133
A kiltermódszer hatékonyságának elméleti javítása	146
A folyamok egészértékűsége és az unimoduláris tulajdonság	147
Tervütemezési alkalmasságok	153
Átrakási és szállítási problémák	156
Többkimenetű és többtermékes folyamok	159
Kétrészes párosítás
Bevezetés	169
Feladatok egymásra való visszavezetései és ekvivalenciái	171
A hálózati folyamokra vonatkozó tételek megfelelői	174
A Mendelsohn-Dulmage-tétel	177
Egy párosítási algoritmus	179
Egy speciális eset: a konvex gráfok	181
Max-minpárosítás	182
A magyar módszer a súlyozott párosításra	186
Egy speciális eset: a Gilmore-Gomory-féle párosítás	192
Egy újfajta optimalizálás kritérium: a Gale-Shapley-féle párosítás	195
Általános párosítás
Bevezetés	201
Különféle problémák	202
Kétirányú folyamatok	206
Növelő utak	209
Fák és kelyhek	211
A párosítási algoritmus	215
A dualitáselmélet	220
A súlyozott párosítási probléma lineáris programozási megfogalmazása	222
Egy O(n4) nagyságrendű párosítási algoritmus	226
Egy O(n3) nagyságrendű párosítási algoritmus	231
A kínai postás problémája	236
A matroidok és a mohó algoritmus
Bevezetés	241
Három, látszólag nem kapcsolódó optimalizációs feladat	242
A matroiddal kapcsolatos definíciók	244
Párosítási, transzverzális és particiós matroidok	247
A matroidok axiómarendszerei	249
A matroidokra vonatkozó mohó algoritmus	251
A mohó algoritmus alkalmazásai	253
Matroiddualitás	254
A mohó algoritmus változatai	257
R. C. Prim algoritmusa a feszítőfára	259
Egy alkalmazás: hálózatok szintézise	260
A Steiner-probléma és más dilemmák	263
Matroidmetszetek
Bevezetés	273
A feladatok kitűzése	274
Növelő sorozatok és szegélygráfok	277
A közönséges metszet algoritmusa	284
A dualitáselmélet	285
Általánosított Mendelsoh-Dulmage-tétel; matroidok összegei és matroidok partíicói	287
Matroidok partíciós algoritmusa	290
A Shannon-féle kapcsolójáték	293
Súlyozott növelő sorozatok	295
Primál súlyozott metszetre vonatkozó algoritmus	299
Matroid poliéderek	302
A primál-duál módszer magyarázata	306
A primál-duál súlyozott metszetre vonatkozó algoritmus	311
Egy speciális eset: irányított feszítőfák	313
A matroid ikerprobléma
Bevezetés	321
Problémák kitűzése	323
Növelő sorozatok	327
Általánosítások	328
Függelék
Bevezetés	331
Részbenrendezett halmazok láncai és antiláncai	331
A súlyozott matroid metszetére vonatkozó egyszerűsített algoritmus	341
Irányított vágások lefogása	347
Életidegen irányított fák	356