Kombinatorikus optimalizálás

Hálózati folyamok, Ford-Fulkerson-algoritmus, egészértékűségi lemma, a folyamprobléma egyszerű általánosításai.

Páros gráfok karakterizációja, maximális méretű párosítás páros gráfban. Kőnig, Frobenius és Hall tételei.

Gráfszínezések. Alsó és felső korlát a kromatikus számra. Gráfok élszínezése, Vizing tétele. Páros gráfok élszínezése az egészértékűségi lemma segítségével

Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban.

Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata, kétváltozós feladatok megoldása grafikus módszerrel. Lineáris egyenlőtlenségrendszerek megoldása Fourier-Motzkin eliminációval. Szükséges és elégséges feltételek lineáris egyenletrendszerek nemnegatív változókkal való, illetve lineáris egyenlőtlenségrendszerek megoldhatóságára: a Farkas-lemma.

A lineáris programozás alapfeladata mátrixos alakban. Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. Lineáris program duálisának fogalma, különféle alakban felírt lineáris programok duálisai.

A lineáris programozás dualitástétele. A lineáris programozás feladatának algoritmikus bonyolultsága. Az egészértékű programozás alapfeladata, annak bonyolultsága. Optimalizálási problémák formalizálása egészértékű programozási feladatként.

Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások a páros gráfok párosításainak és a hálózati folyamproblémák területéről: maximális folyam, minimális költségű folyam, ill. többtermékes folyam feladatok.

Lokális él- és pontösszefüggőség, illetve globális él- és pontösszefüggőség fogalma, a vonatkozó Menger-tételek (ismétlés). Max-vissza sorrend, Nagamochi-Ibaraki algoritmusa az élösszefüggőség meghatározására.

Algoritmus gráfok 2-élösszefüggővé növelésére, alsó becslés a szükséges élek számára. Algoritmus minimális költségű feszítő fenyő keresésére. Fülfelbontás, gráfok erősen összefüggővé irányítása.

Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával, leghosszabb kör additív hibával való közelíthetetlensége. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára.

Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FD és FFD heurisztikák a ládapakolási problémára.

Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.