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: 2014. október 1.

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

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

    Számításelmélet mellékspecializáció

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMB00 3 2/1/0/v 4  
    3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
    A tantárgy tanszéki weboldala http://www.cs.bme.hu/ghinf/
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egyetemi tanár

    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

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

    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZM231" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM231", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZMA15", "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA15", "FELVETEL", AktualisFelev()) > 0)

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

    1)      Általános bevezetés. Hipergráfok fogalma és ekvivalens megadásai. Hipergráfok mint gráfok általánosításai, halmazrendszerek, bináris sorozatok halmazai, kódok.  Példák. Ryser sejtés, Baranyai tétel kimondása.

     

    2)      Baranyai tétel bizonyítása: Kerekítési lemma, ekvivalens állítás kimondása az indukcióhoz, indukciós bizonyítás. Stabil párosítások fogalma, Gale-Shapley tétel,  algoritmus stabil párosítás keresésére páros gráfokban.

     

    3)      Nevezetes extremális halmazelméleti eredmények I: Sperner-tétel, LYM-egyenlőtlenség, Bollobás-egyenlőtlenség, Ahlswede-Zhang azonosság. Lexikografikus és kolexikografikus rendezés, Kruskal-Katona tétel kimondása.

     

    4)      Pozitív egész számok r-binomiális fölírása, balra tolás.  Kruskal-Katona tétel bizonyítása. Nevezetes extremális halmazelméleti eredmények II: Erdős-Ko-Rado tétel, bizonyítása a Kruskal-Katona tétel felhasználásával (Daykin féle bizonyítás).

     

    5)      Erdős-Ko-Rado tétel Katona féle bizonyítása. Lineáris algebra alkalmazása extremális halmazelméleti eredmények bizonyítására: Páratlanváros tétel és Párosváros tétel.

     

    6)      Lineáris algebra további kombinatorikai alkalmazásai: Graham-Pollak tétel (Tverberg bizonyításával), Borsuk sejtés és Kahn-Kalai féle cáfolata (Nilli féle bizonyítással).

     

    7)      Kneser-sejtés, Kneser gráfok, Lovász-Kneser tétel. Borsuk-Ulam tétel, ekvivalens alakjai, Lusterrnik-Schnirelmann verzió, Lovász-Kneser tétel Greene féle bizonyítása. Dolnyikov tétele Matousek bizonyításával.

     

    8)      Schrijver gráfok, Schrijver tétele. Bizonyításhoz Gale lemma Ziegler féle bizonyítással és a Lovász-Kneser tétel Bárány féle bizonyítása. Színkritikusság.

     

    9)      Erdős-Katona sejtés, Frankl-Füredi féle felső korlát, Shearer konstrukció, a probléma további története, kapcsolat a bináris szorzócsatornával, Tolhuizen tétele.

     

    10)   Ramsey típusú tételek. Ramsey tétele gráfokra és uniform hipergráfokra. Geometriai alkalmazások. Ramsey számok meghatározásának nehézsége. Erdős-Hajnal kérdés. Indukált Ramsey tétel.

    .

    11)   Chvátal pontos Ramsey számot adó tétele fákról és teljes gráfokról. Chvátal „art gallery"  tétele.

     

    12)   Lokális kromatikus szám. Viszonya a kromatikus számhoz.

     

    13)   Híres sejtések. Hadwiger sejtés, gyengített változat, Reed-Seymour tétel. Hedetniemi sejtés, gyengített változat. Poljak-Rödl tétel, El Zahar-Sauer tétel. További variációk.

    Erdős-Faber-Lovász sejtés.

     

    14)   Reed sejtés, Behzad-Vizing sejtés. Áttekintés, összefoglalás, tartalék.

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

    Heti 2 óra előadás és heti 1 órás (kéthetente 2  órás) gyakorlat.

     


    10. Követelmények

    Vizsgaidőszakban: szóbeli vizsga.

    Szorgalmi időszakban: Öt kiszárthelyi (10 -15 perces) dolgozat a gyakorlatokon, az aláiráshoz ezekből legalább hármat megfelelt szinten kell megirni.

    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 óra42
    Félévközi készülés órákra30
    Felkészülés zárthelyire8
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés42
    Összesen120
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egyetemi tanár

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