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

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

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

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

    Mérnök informatikus szak, MSc képzés

    Számításelmélet szakirány

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM231 2 2/1/0/v 4  
    3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás, Számítástudományi és Információelméleti Tanszék
    4. A tantárgy előadója Dr. Simonyi Gábor egyetemi docens
    5. A tantárgy az alábbi témakörök ismeretére épít Alapvető gráfelméleti fogalmak, lineáris algebra alapjai
    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZMB00" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMB00", "FELVETEL", AktualisFelev()) > 0)

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

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    Ajánlott:
    Ezt a tárgyat nem vehetik fel, akik a VISZM032 kódú “Gráfok, hipergráfok és alkalmazásaik – matematikusoknak” 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

    Párosítási és élszínezési eredmények, stabil párosítások, Gale-Shapley tétel és alkalmazása felvételi és egyéb pályázati rendszerekben.

    Listaszínezés, listaszínezési sejtés, Galvin-tétel, síkgráfok listaszínezése

    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: Sperner-tétel, LYM-egyenlőtlenség, Bollobás-egyenlőtlenség, Ahlswede-Zhang azonosság, Erdős-Ko-Rado tétel, Kruskal-Katona tétel

    Ramsey tétele gráfokra és hipergráfokra, geometriai alkalmazások

    Lineáris algebra alkalmazására példák: Fisher-egyenlőtlenség, 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.

    További geometriai alkalmazások: Chvátal "art gallery" tétele, Borsuk-sejtés Kahn-Kalai-Nilli féle cáfolata

    Részben rendezett halmazok, Dilworth-tétel, perfekt gráfok és poliéderes jellemzésük, imperfektségi hányados, kapcsolat frekvenciakiosztási problémákkal.

     

    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: öt kiszárthelyi (10-15 perces) dolgozat a gyakorlatokon; az aláíráshoz ezekből legalább hármat megfelelt szinten kell teljesíteni

    vizsgaidőszakban: szóbeli vizsga

    11. Pótlási lehetőségek A kiszárthelyik pótlására nincs mód.
    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 óra 42
    Félévközi készülés órákra30
    Felkészülés zárthelyire 
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés48
    Összesen120
    15. A tantárgy tematikáját kidolgozta Dr. Simonyi Gábor egyetemi docens