K-INFO
HU
EN
Belépés
Tantárgy » BMEVISZMA15
Régebbi verziók TAD letöltése (PDF)

Gráfok, hipergráfok és alkalmazásaik

Graphs, Hypergraphs and Their Applications 
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
Tantárgy neve (magyarul, angolul)
Gráfok, hipergráfok és alkalmazásaik
Graphs, Hypergraphs and Their Applications 
Tantárgykód BMEVISZMA15
Tantárgyjelleg —
Képzési szint —
Kurzustípusok és óraszámok (heti/féléves)
Kurzustípus elmélet gyakorlat laboratóriumi gyakorlat
óraszám (heti) 2 1 0
jelleg (kapcsolt/önálló) — kapcsolt —
Tanulmányi teljesítmény/értékelés típusa vizsga
Tantárgy kreditértéke 5
Tantárgyfelelős
Dr. Simonyi Gábor
elérhetőség: simonyi@math-inst.hu
Tantárgyat gondozó oktatási szervezeti egység
Számítástudományi és Információelméleti Tanszék
Kar Villamosmérnöki és Informatikai Kar
Tantárgy weboldala http://cs.bme.hu/ghinf/
Tantárgy elsődleges mintatantervi jellege —
Közvetlen előkövetelmények – Erős előkövetelmény nincs
Közvetlen előkövetelmények – Gyenge előkövetelmény nincs
Közvetlen előkövetelmények – Párhuzamos előkövetelmény nincs
Közvetlen előkövetelmények – Mérföldkő előkövetelmény nincs
Közvetlen előkövetelmények – Kizáró feltétel nincs

Célkitűzés

Tantárgyprogram

  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 

 

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.  

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

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. 

Tanulástámogató anyagok

Online források
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.  

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Alapvető gráfelméleti fogalmak, lineáris algebra alapjai (Bevezetés a számításelméletbe 1-2) 
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Alapvető gráfelméleti fogalmak, lineáris algebra alapjai (Bevezetés a számításelméletbe 1-2) 
Általános szabályok
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  Pótlási lehetőségek: A kiszárthelyik pótlására nincs mód. 
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

Nincs megadva.

A tantárgy elvégzéséhez szükséges tanulmányi munka

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.