Fiala Tibor
Kombinatorikus optimalizálás
TARTALOM, BEVEZETÉS
Tartalom
Bevezetés
1. Gráfelméleti alapok
1.1. Alapfogalmak
1.2. Fák jellemzése
1.3. Páros gráfok
1.4. Euler-gráfok
2. Maximális folyam, minimális vágás
2.1. Folyam és vágás
2.2. A Ford-Fulkerson-algoritmus
3. A Ford-Fulkerson-algoritmus kombinatorikai következményei
3.1. Menger tételei
3.2. A Kőnig-tétel
3.3. Teljes párosítások páros gráfban
4. Párosítások páros gráfban
4.1. Optimalitási kritérium
4.2. Maximális párosítás páros gráfban algoritmus
4.3. A párosítás és teljes párosítás politópok
5. Súlyozott párosítások páros gráfban
5.1. Maximális összsúlyú párosítás
5.1.1. algoritmus
5.1.2. A maximumfeladat duálisa
5.2. Maximin párosítás
5.3. Minimális összsúlyú teljes párosítás
5.3.1. A minimumfeladat duálisa
5.3.2. Primál-duál-algoritmus
6. Maximális párosítások nempáros gráfban
6.1. Maximális párosítás
6.2. Páratlan ponthalmaz fedés (odd set cover)
6.3. Pontok fedése élekkel
7. Optimális súlyozott párosítások nempáros gráfban
7.1. Különböző optimumfeladatok
7.2. Minimális súlyú teljes párosítás primál-duál algoritmussal
7.3. Az Edmonds-féle párosítás politópok
7.4. A kínai postás feladat
8. Matroidok
8.1. Alapfogalmak
8.2. A mohó algoritmus
8.3. A matroid politóp
9. Teljesen unimoduláris mátrixok
9.1. Alapvető tulajdonságok
9.2. Teljesen unimoduláris pont-él mátrixok
9.3. Alkalmazások
Összefoglalás
Függelék
A. Poliéder és politóp
B. A Bn vektortér
Név- és tárgymutató
Irodalomjegyzék
Bevezetés
Ez a kis könyv azoknak az előadásoknak az anyagát tartalmazza, melyeket a szerző kombinatorikus optimalizálás témakörben a Corvinus Egyetem operációkutatás szakirányos hallgatóinak tartott. Ezzel a címmel az első összefoglalómű Lawler 1976-ban megjelent könyve volt, melyre jelentős mértékben támaszkodunk. A témakör nagy összefoglaló monográfiája Schrijver 2003-ben publikált könyve, amiből elsősorban a poliéder-politópos megközelítést tartjuk követendőnek. Ugyancsak Schrijvertől származik az a kisebb lélegzetű tanfolyami anyag, amelyik sok témában tárgyalásunk vezérfonalát képezi.
Az első fejezetben gráfelméleti alapfogalmakat ismertetünk. A második fejezet a maximális folyam, minimális vágás témakörben alapvető jelentőségű Ford-Fulkerson-algoritmussal foglalkozik. A 3. fejezetben a Ford-Fulkerson-algoritmus következményeként tárgyaljuk a Menger-tételeket, valamint a páros gráfokra vonatkozó Kőnig-tételt.
Páros gráfok maximális párosításainak és minimális lefogó rendszereinek keresése a kombinatorika klasszikus feladata. Ezt ismerteti a 4. fejezet. Az 5. fejezetben páros gráfok súlyozott párosításaival foglalkozunk. Nempáros gráfban a maximális párosítás előállítása Edmonds kontrakciós algoritmusán alapul, ezt tárgyaljuk a 6. fejezetben. A 7. fejezetben az optimális súlyozott párosításokat vizsgáljuk ugyancsak nempáros gráfokban. A 8. fejezetben ismerkedhetünk meg a matroidokkal kapcsolatos alapvető tudnivalókkal. Végül a 9. fejezetben tárgyaljuk a teljesen unimoduláris mátrixok témakörét, természetesen kombinatorikai alkalmazásokkal.
Alapvető jelentőségű az A. függelék, amelyik a poliéderekkel illetve politópokkal kapcsolatos tudnivalókat foglalja össze. Nevezetes tény, hogy a poliéder és a politóp ugyanaz a fogalom. Az egyetemen a tárgy oktatását ezzel szoktam kezdeni, itt csak azért került a függelékbe, mert ez inkább a konvex analízis témakörébe tartozik.
Köszönetet mondok Szegő Lászlónak az első hét fejezet gondos lektorálásáért és értékes javaslataiért. Köszönetet mondok Forgó Ferencnek, Solymosi Tamásnak és Temesi Józsefnek egy-egy fejezet lektorálásáért. Hálával tartozom Fiala Péternek, aki a munka során szakmai és didaktikai szempontból egyaránt magas színvonalon mutatta az utat a LATEX ösvényein.