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ó    

    Gráfok, hipergráfok és alkalmazásaik - matematikusoknak

    A tantárgy angol neve: Graphs, Hypergraphs and Their Applications

    Adatlap utolsó módosítása: 2010. június 10.

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

    Matematikus szak, MSc képzés

    Diszkrét matematika blokk
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM032 3 3/1/0/f 5  
    3. A tantárgyfelelős személy és tanszék Fleiner Tamás,
    4. A tantárgy előadója Dr. Simonyi Gábor, VIK Számítástudományi és Infromációelméleti Tanszék  egyetemi tanár
    5. A tantárgy az alábbi témakörök ismeretére épít

    Alapvető gráfelméleti fogalmak, a lineáris algebra alapjai

    6. Előtanulmányi rend
    Kötelező:
    NEM (TárgyTeljesítve("BMEVISZM231") )

    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:
    Ezt a tárgyat nem vehetik fel, akik a VISZM231 kódú “Gráfok, hipergráfok és alkalmazásaik – informatikusoknak” című tárgyat teljesítették.
    7. A tantárgy célkitűzése

    A tárgy fő célja a hallgatók gráfelméleti ismereteinek bővítése, a hipergráfok elmélete néhány fontosabb eredményének bemutatása és ezáltal a diszkrét matematikai gondolkodás fejlesztése. Hangsúlyosan be kívánja mutatni a hipergráf fogalom különféle nézőpontjait (gráfok általánosításai, halmazrendszerek, az élek
    karakterisztikus vektorainak halmazai, kódok), megismertetni a különböző nézőpontok előnyeit és rutinszerűvé tenni a közöttük való átjárást. Ezzel összefüggő cél a hallgatók azon készségének fejlesztése, hogy a gyakorlatban felmerülő problémák felvetette elméleti kérdéseket észrevegyék és meg tudják fogalmazni.

     

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

    Hipergráfok fogalma, nézőpontjai: gráfok általánosításai, halmazrendszerek, 0-1 sorozatok halmazai, bináris kódok. Gráfelméleti eredmények általánosításai: Baranyai tétele, Ryser-sejtés. Nevezetes extremális halmazelméleti eredmények: Ahlswede-Zhang azonosság, Kruskal-Katona tétel.

    Ramsey típusú tételek indukált Ramsey tétel. Lineáris algebra alkalmazására példák: Páratlanváros-tétel, Frankl-Wilson tétel, Graham-Pollak tétel. Erdős-Katona sejtés és Shearer-féle cáfolata, a probléma kódelméleti interpretálása, bináris szorzócsatorna kapacitástartománya, Frankl-Füredi és Tolhuizen vonatkozó eredményei. Geometriai alkalmazások: Chvátal "art gallery" tétele, Borsuk-sejtés Kahn-Kalai-Nilli féle cáfolata. Lovász-Kneser tétel, Dolnyikov-tétel, Schrijver tétele.
    Perfekt gráfok hipergráfos és poliéderes jellemzése.
     

    A gyakorlatokon elsősorban az anyag feladatok megoldásán keresztül való elmélyítése a cél. E feladatok egy része az alkalmazási lehetőségek hangsúlyozására is alkalmat ad.

     

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

    • Szorgalmi időszakban:  5 kiszárthelyi (10-15 perces) és  1  zárthelyi dolgozat. A 3 legjobb kis zh adja a jegy 40%-át, a zárthelyi dolgozat a 60%-át.

    • Vizsgaidőszakban: -

     

    11. Pótlási lehetőségek

    A kis zh-k nem pótolhatóak.

    A zárthelyi dolgozathoz egy pótlási lehetőség lesz  a  szorgalmi időszakban és egy  a pótlási héten.

     

    12. Konzultációs lehetőségek Előzetes egyeztetés szerint.
    13. Jegyzet, tankönyv, felhasználható irodalom A tárgyalandó eredmények közül több megtalálható az alábbi kötetben:
    M. Aigner, G. M. Ziegler: Bizonyítások a KÖNYVből, Typotex Kiadó, 2004.
    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ákra44
    Felkészülés zárthelyire50
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés 
    Összesen150
    15. A tantárgy tematikáját kidolgozta Dr. Simonyi Gábor egyetemi tanár