Tantárgy » BMEVISZA028
Gráfok és algoritmusok
Graphs and Algorithms
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 és algoritmusok
Graphs and Algorithms
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tantárgykód | BMEVISZA028 | ||||||||||||
| 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
Tantárgyprogram
Algoritmikus bizonyítások: mohó technikák, javító utak, helyi javítások, elemi konstrukciók
Stabil párosítások, Gale--Shapley-algoritmus, stabil párosítások hálótulajdonsága. Alkalmazások: utak linking tulajdonsága, Galvin listaszínezési tétele, Alon--Tarsi-tétel páros síkgráfok listaszínezéséről, a Sands-Sauer-Woodrow-tétel, aciklikus digráf magvassága
Stabil párosítások nem páros gráfokon: Irving algoritmusa. Stabil félpárosítások és a Scarf-lemma.
Minimális vágások keresése, a Nagamochi--Ibaraki-algoritmus (maxvissza sorrend), merevkörű gráfok, szimpliciális csúcs, merevkörű gráfok listaszínezése, Karger algoritmusa.
Lamináris halmazrendszerek reprezentációja, minimális vágások reprezentációja, a Gomory-Hu fa és a kaktuszreprezentáció.
Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok
Lovász leemelési tétele, 2k-élösszefüggő gráfok előállítása, Nash-Williams irányítási tétele,
Áramok és folyamok, Hoffmann-tétel, algoritmus minimális költségű folyam keresésére
Az egészértekűségi lemma alkalmazásai (páros gráfok élszínezése, folyamok kerekíthetősége, Baranyai tétele)
Stabil párosítások, Gale--Shapley-algoritmus, stabil párosítások hálótulajdonsága. Alkalmazások: utak linking tulajdonsága, Galvin listaszínezési tétele, Alon--Tarsi-tétel páros síkgráfok listaszínezéséről, a Sands-Sauer-Woodrow-tétel, aciklikus digráf magvassága
Stabil párosítások nem páros gráfokon: Irving algoritmusa. Stabil félpárosítások és a Scarf-lemma.
Minimális vágások keresése, a Nagamochi--Ibaraki-algoritmus (maxvissza sorrend), merevkörű gráfok, szimpliciális csúcs, merevkörű gráfok listaszínezése, Karger algoritmusa.
Lamináris halmazrendszerek reprezentációja, minimális vágások reprezentációja, a Gomory-Hu fa és a kaktuszreprezentáció.
Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok
Lovász leemelési tétele, 2k-élösszefüggő gráfok előállítása, Nash-Williams irányítási tétele,
Áramok és folyamok, Hoffmann-tétel, algoritmus minimális költségű folyam keresésére
Az egészértekűségi lemma alkalmazásai (páros gráfok élszínezése, folyamok kerekíthetősége, Baranyai tétele)
A tantárgy néhány olyan, a gráfelmélethez szorosan kapcsolódó területet igyekszik bemutatni, amelyekre egy bevezető kurzuson rendszerint nem jut idő. Az vizsgált problémák megoldásában az algoritmikus megközelítés kiemelt szerepet kap.
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 előadás + 2 gyakorlat
Tanulástámogató anyagok
Online források
Frank; András: Diszkrét optimalizálás; Frank András:; Gráfelmélet; (online jegyzetek)
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)
Gráfok,
elemi algoritmusok
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)
Gráfok,
elemi algoritmusok
Általános szabályok
Követelmények:
2 zárthelyi
számonkérés. Aláírás feltétele: mindkettő legalább elégséges.
Szóbeli vizsga az aláírással rendelkezőknek. Érdemjegy súlyozása: ZH 40%, szóbeli 60%.
Pótlási lehetőségek:
TVSZ szerint
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
Kombinatorika és Gráfelmélet 1. BMEVISZA025 vagy
A számítástudomány alapjai BMEVISZAA05 vagy
Bevezetés a számításelméletbe 2. BMEVISZAA04
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.