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) 

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 rend az adott szak honlapján és képzési programjában található.

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