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ó    

    Kombinatorika és gráfelmélet 2

    A tantárgy angol neve: Combinatorics and Graph Theory 2

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

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

    TTK

    Matematika BSc

    Elméleti specializácó 
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZA026   2/2/0/v 4 5
    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

    Dr. Tóth Géza, egyetemi docens

    5. A tantárgy az alábbi témakörök ismeretére épít Alapvető gráfelméleti fogalmak és 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 

    8. A tantárgy részletes tematikája

    Geometriai és absztrakt dualitás, gyenge izomorfia (2-izomorfia), Whitney tételei.

    Pont- és élszínezési alapfogalmak, Mycielsky-konstrukció, Brooks-tétel.

    Ötszíntétel.

    Vizing-tétel, élszínezés kapcsolata teljes párosításokkal, Petersen-tétel.

    Listaszínezés, Galvin-tétel.

    Perfekt gráfok, intervallumgráfok, Perfekt gráf tétel.

    Ramsey-tétel, Erdős-Szekeres-tétel, Erdős-féle alsó becslés, valószínűségszámítási módszer.

    Turán-tétel, Erdős-Stone-tétel, Erdős-Simonovits-tétel.

    Hipergráfok, Erdős-Ko-Rado-tétel, Sperner-tétel, LYM-egyenlőtlenség.

    De Bruijn-Erdős-tétel, véges síkok, konstrukciójuk véges testből, differencia-halmazokból.

    Generátorfüggvények, Fibonacci-számok, Catalan-számok.

    Részben rendezett halmazok, Dilworth-tétel.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 2 óra előadás és heti 2 óra gyakorlat.
    10. Követelmények

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

    Vizsgaidőszakban szóbeli vizsga. Érdemjegy súlyozása: zh 40%, házi feladat 10%, szóbeli vizsga 50%.

    11. Pótlási lehetőségek TVSZ szerint (Egy zárthelyi pótolható)
    12. Konzultációs lehetőségek Igény szerint.
    13. Jegyzet, tankönyv, felhasználható irodalom

    Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány elemei, Typotex, Budapest, 2002

    Friedl Katalin, Recski András, Simonyi Gábor: Gráfelmélet példatár, Typotex, Budapest, 2006.

    Fleiner Tamás: A számítástudomány alapjai,  http://www.cs.bme.hu/~fleiner/jegyzet/NESZ.pdf

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra56
    Félévközi készülés órákra28
    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

    Dr. Tóth Géza, egyetemi docens