BME VIK - Gráfok és algoritmusok

3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,

4. A tantárgy előadója Dr. Fleiner Tamás, egyetemi docens

5. A tantárgy az alábbi témakörök ismeretére épít Gráfok, elemi algoritmusok

6. Előtanulmányi rend

Ajánlott:

Kombinatorika és Gráfelmélet 1. BMEVISZA025 vagy

A számítástudomány alapjai BMEVISZAA05 vagy

Bevezetés a számításelméletbe 2. BMEVISZAA04

7. A tantárgy célkitűzése

A tantárgy néhány olyan, a gráfelmélethez szorosan kapcsolódó területet igyekszik bemutatni, amelyekre egy bevezető kurzuson rendszerint nem jut idő. Az vizsgált problémák megoldásában az algoritmikus megközelítés kiemelt szerepet kap.

8. A tantárgy részletes tematikája Algoritmikus bizonyítások: mohó technikák, javító utak, helyi javítások, elemi konstrukciók

Stabil párosítások, Gale--Shapley-algoritmus, stabil párosítások hálótulajdonsága. Alkalmazások: utak linking tulajdonsága, Galvin listaszínezési tétele, Alon--Tarsi-tétel páros síkgráfok listaszínezéséről, a Sands-Sauer-Woodrow-tétel, aciklikus digráf magvassága

Stabil párosítások nem páros gráfokon: Irving algoritmusa. Stabil félpárosítások és a Scarf-lemma.

Minimális vágások keresése, a Nagamochi--Ibaraki-algoritmus (maxvissza sorrend), merevkörű gráfok, szimpliciális csúcs, merevkörű gráfok listaszínezése, Karger algoritmusa.

Lamináris halmazrendszerek reprezentációja, minimális vágások reprezentációja, a Gomory-Hu fa és a kaktuszreprezentáció.

Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok

Lovász leemelési tétele, 2k-élösszefüggő gráfok előállítása, Nash-Williams irányítási tétele,

Áramok és folyamok, Hoffmann-tétel, algoritmus minimális költségű folyam keresésére

Az egészértekűségi lemma alkalmazásai (páros gráfok élszínezése, folyamok kerekíthetősége, Baranyai tétele)

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 2 előadás + 2 gyakorlat

10. Követelmények

2 zárthelyi számonkérés. Aláírás feltétele: mindkettő legalább elégséges.

Szóbeli vizsga az aláírással rendelkezőknek. Érdemjegy súlyozása: ZH 40%, szóbeli 60%.

11. Pótlási lehetőségek TVSZ szerint

12. Konzultációs lehetőségek Vizsgaalkalmak előtt

13. Jegyzet, tankönyv, felhasználható irodalom

Frank András: Diszkrét optimalizálás

Frank András: Gráfelmélet

(online jegyzetek)

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	56
Félévközi készülés órákra	28
Felkészülés zárthelyire	8
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	28
Összesen	120

15. A tantárgy tematikáját kidolgozta Dr. Fleiner Tamás, egyetemi docens