Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    Gráfok és algoritmusok

    A tantárgy angol neve: Graphs and Algorithms

    Adatlap utolsó módosítása: 2018. október 9.

    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 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