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 1

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

    Adatlap utolsó módosítása: 2015. november 9.

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

    TTK

    Matematika BSc szak
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZA025   2/2/0/v 6 2
    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

    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZAA01" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAA01", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAA02" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAA02", "FELVETEL", AktualisFelev()) > 0 )

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    Ajánlott:
    Villamosmérnöki és mérnökinformatikus szakos hallgatók nem vehetik fel.
    8. A tantárgy részletes tematikája

    Leszámlálások (permutációk, variációk, kombinációk, binomiális tétel, binomiális együtthatókra vonatkozó tételek). Nevezetes leszámlálási módszerek, skatulya-elv, szita-módszer.

    Gráfelméleti alapfogalmak (pont, él, fokszám, izomorfia, út, kör, összefüggőség). Fák, Cayley-tétel, Prüfer-kód. Mohó algoritmus, Kruskal-tétel. Páros gráfok, jellemzésük. Párosítások, Kőnig-Hall-Frobenius-tétel, Tutte-tétel, Gallai tételei, Kőnig tételei. Hálózati folyamok, Ford-Fulkerson-tételek, Edmonds-Karp-tétel.

    Menger tételei, gráfok magasabb pont- és él-összefüggőségi számai, Dirac-tétel.

    Euler-bejárások, Euler-tétele.

    Hamilton-körök és utak, létezésük szükséges feltétele. Elégséges feltételek (Dirac, Ore, Pósa és Chvatal tételei).

    Síkbarajzolhatóság, viszonya a gömb és a tórusz felszínére való rajzolhatósághoz, sztereografikus projekció, Euler-formula. Kuratowski-tétel, Fáry-Wagner-tétel.

    Szélességi és mélységi keresés, legrövidebb utak megkeresése (Dijkstra, Ford, Floyd algoritmusok), PERT-módszer.

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

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

    Vizsgaidőszakban: szóbeli vizsga az aláírással rendelkezőknek. Érdemjegy súlyozása: ZH 40%, házi feladat 10%, szóbeli 50%.

    11. Pótlási lehetőségek TVSZ szerint (Egy sikertelen 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ákra56
    Felkészülés zárthelyire20
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés48
    Összesen180
    15. A tantárgy tematikáját kidolgozta

    Dr. Fleiner Tamás, egyetemi docens

    Dr. Tóth Géza, egyetemi docens