Gráfok, hipergráfok és alkalmazásaik
A tantárgyleírás hatályossága
| Tantárgy neve (magyarul, angolul) |
Gráfok, hipergráfok és alkalmazásaik
Graphs, Hypergraphs and Their Applications
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tantárgykód | BMEVISZM231 | ||||||||||||
| Tantárgyjelleg | — | ||||||||||||
| Képzési szint | — | ||||||||||||
| Kurzustípusok és óraszámok (heti/féléves) |
|
||||||||||||
| Tanulmányi teljesítmény/értékelés típusa | vizsga | ||||||||||||
| Tantárgy kreditértéke | 4 | ||||||||||||
| 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 | — | ||||||||||||
| 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
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életi
interpretálása, bináris szorzócsatorna kapacitástartománya, Frankl-Füredi és
Tolhuizen 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.
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
Tanulástámogató anyagok
Online források
A tantárgy teljesítéséhez ajánlott előzetes ismeretek
Általános szabályok
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
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
Tantervi elhelyezés
Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.