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: 2006. július 1.

    Tantárgy lejárati dátuma: 2015. január 31.

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

    TTK

    Alkalmazott matematikus szak

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMA0175 2. 2/0/0/f 2 2/2
    3. A tantárgyfelelős személy és tanszék Dr. Recski András,
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egy. docens

    Számítástudományi és Információelméleti Tanszék

    5. A tantárgy az alábbi témakörök ismeretére épít

    -

    6. Előtanulmányi rend
    Kötelező:
    TárgyEredmény( "BMEVIMA0173" , "jegy" , _ ) >= 2

    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:

    Kombinatorika és Gráfelmélet 1. (bmevima0173)

    Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:

    bmevima1824 Kombinatorika és Gráfelmélet II.

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

    Bevezetés a diszkrét matematika elemeibe és módszereibe.

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

    Feladatok megoldása az alábbi témákban: Szélsőérték-problémák, extrém gráfok: Turán-típusú tételek, Erdős-Gallai tételek. Ramsey-számok, Erdős-Szekeres tétel. Síkbarajzolhatóság (Euler-formula, Kuratowski, Wagner és Fáry tételei). Adjacencia-, incidencia-, kör- és vágatmátrix. Duálgráfok, 2-izomorfia, Whitney tételei. Ötszíntétel, Tait tétele. Perfekt gráfok, listaszínezés. Gráfok spektruma. Rekurziók és generátorfüggvények: Fibonacci számok, Stirling számok, Bell-számok, számelméleti partíciók, Catalan számok. Lineáris- és másodrendű rekurziók. Extremális halmazrendszerek. Erdős-Ko-Rado tétel. Sperner-rendszerek.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    gyakorlat

    10. Követelmények

    a. A szorgalmi időszakban: Az elégséges gyakorlati jegy feltétele mindkét félévközi zárthelyi legalább elégséges szinten való megírása. A végső gyakorlati jegy megállapításakor a két zárthelyi eredményén kívül a házi feladatokban és az órai szereplésben nyújtott teljesítményt is figyelembe vesszük.

    b. A vizsgaidőszakban: -

    c. Elővizsga: -

    13. Jegyzet, tankönyv, felhasználható irodalom

    Katona Gyula, Recski András: Bevezetés a véges matematikába, 1993

    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    vima0175gy.rtf

    egy. tanár

    Számítástudományi és Információelméleti Tanszék