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: 2023. január 12.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar     		MSc, Mérnökinformatikus
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA15   2/1/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Simonyi Gábor,
    A tantárgy tanszéki weboldala http://cs.bme.hu/ghinf/
    4. A tantárgy előadója Dr. Simonyi Gábor egyetemi tanár, SZIT
    5. A tantárgy az alábbi témakörök ismeretére épít

    Alapvető gráfelméleti fogalmak, lineáris algebra alapjai (Bevezetés a számításelméletbe 1-2) 

    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

    1. 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. 

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

    1. Hipergráfok fogalma, nézőpontjai: gráfok általánosításai, halmazrendszerek, 0-1 sorozatok halmazai, bináris kódok 

    1. Gráfelméleti eredmények általánosításai: Baranyai tétele, Ryser-sejtés 

    1. 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 

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

    1. Lineáris algebra alkalmazására példák: Fisher-egyenlőtlenség, Páratlanváros-tétel,  

    1. Frankl-Wilson tétel, Graham-Pollak tétel 

    1. 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,  

    1. Frankl-Füredi és Tolhuizen vonatkozó eredményei. 

     

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

    1. 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. 

    1. Ismétlés, tartalék 

     

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Előadás és gyakorlat. Egyes bizonyítások részleteit a hallgatók a kijelölt írásos anyagból sajátítják el. 
    10. Követelmények

    Szorgalmi időszakban: 5 kiszárthelyi (mindegyik 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 Az előadóval való 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 óra42
    Félévközi készülés órákra28
    Felkészülés zárthelyire15
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása23
    Vizsgafelkészülés42
    Összesen150
    15. A tantárgy tematikáját kidolgozta Dr. Simonyi Gábor egyetemi tanár, SZIT