Gráfok és algoritmusok

A tantárgy angol neve: Graphs and Algorithms

Adatlap utolsó módosítása: 2018. július 8.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Matematika BSc

Elméleti és alkalmazott specializáció 

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZA028   2/2/0/v 4 6
3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás, Számítástudományi és Információelméleti Tanszék
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
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