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

BMEVISZMB00

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

Tantárgyfelelős

Fleiner Tamás

beosztás: egyetemi tanár

elérhetőség: fleiner.tamas@vik.bme.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://www.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) Á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.

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

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

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

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

Általános szabályok

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

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.

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.