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)

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

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