Belépés címtáras azonosítással
magyar nyelvű adatlap
Gráfok, hipergráfok és alkalmazásaik
A tantárgy angol neve: Graphs, Hypergraphs and Their Applications
Adatlap utolsó módosítása: 2010. június 11.
Mérnök informatikus szak, MSc képzés
Számításelmélet szakirány
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ó.
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 élekkarakterisztikus 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.
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.
Listaszínezés, listaszínezési sejtés, Galvin-tétel, síkgráfok listaszínezése
Hipergráfok fogalma, nézőpontjai: gráfok általánosításai, halmazrendszerek, 0-1 sorozatok halmazai, bináris kódok
Gráfelméleti eredmények általánosításai: Baranyai tétele, Ryser-sejtés
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
Ramsey tétele gráfokra és hipergráfokra, geometriai alkalmazások
Lineáris algebra alkalmazására példák: Fisher-egyenlőtlenség, Páratlanváros-tétel, Frankl-Wilson tétel, Graham-Pollak tétel
Erdős-Katona sejtés és Shearer-féle cáfolata, a probléma kódelméletiinterpretálása, bináris szorzócsatorna kapacitástartománya, Frankl-Füredi ésTolhuizen vonatkozó eredményei.
További geometriai alkalmazások: Chvátal "art gallery" tétele, Borsuk-sejtés Kahn-Kalai-Nilli féle cáfolata
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.
A gyakorlatokon elsősorban az anyag feladatok megoldásán keresztül való elmélyítése a cél. E feladatok egy része az alkalmazási lehetőségek hangsúlyozására is alkalmat ad.
szorgalmi időszakban: öt kiszárthelyi (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
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.