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: 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
    VIMA0173 1. 2/1/0/v 4 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Recski András, Számítástudományi és Információelméleti Tanszék
    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
    Ajánlott:

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

    Neptun-kód Cím --

    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

    Elemi leszámlálás: Permutációk, kombinációk, variációk, skatulya-elv, szita-módszer. Fák, minimális költségű feszítő fa. Kruskal algoritmus, Prüfer-kód, Cayley-tétele, Ruler-bejárás. A “kínai postás” probléma. Dirac-Erdős-Pósa-Chvatal tételei. Páros gráfok. König-Hall tétel. Tutte és Petersen tételei. Maximális folyamok: Menger és Ford-Fulkerson tételek. Pont- és élszínezés (alsó és felső korlátok, Mycielski-konstrukció, Broks- és Vízing tétel).

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

    előadás és gyakorlat

    10. Követelmények

    a. A szorgalmi időszakban: 2 zárthelyi minimum elégséges szinten történő teljesítése

    b. A vizsgaidőszakban: szóbeli vizsga

    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

    egy. tanár

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