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

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

    Adatlap utolsó módosítása: 2020. december 15.

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

    TTK

    Matematika MSc

    Diszkrét Matematika blokk
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM022   2/2/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
    A tantárgy tanszéki weboldala https://www.renyi.hu/~geza/kombi2/
    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

    Kizárás:
    BMEVISZA026 Kombinatorika és Gráfelmélet 2.

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

    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.
    hetente 2db 10 pontos beadandó házi feladat, a teljesítés feltétele 40 pont megszerzése

    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 Egy zárthelyi pótolható, házi feladat nem 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ákra18
    Felkészülés zárthelyire8
    Házi feladat elkészítése40
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés28
    Összesen150
    IMSc tematika és módszer

    Dr. Fleiner Tamás, egyetemi docens

    Dr. Tóth Géza, egyetemi docens