BME-MITBevezetés a számításelméletbe 2
VISZAA04 | Mérnökinformatikus BSc | Félév: 2 | Kredit: 5 | Hivatalos tantárgyi adatlap
A tantárgy célkitűzése
Az informatikai tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása. Ezen belül a tantárgy a gráfelmélet egyes területeire nyújt bevezetést és alapvető gráfelméleti algoritmusokat ismertet.
A tantárgyat sikeresen teljesítő hallgató képes lesz:
- (K3) érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;
- (K3) önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;
- (K2) alkalmazni a tárgyban szereplő algoritmusokat;
- (K2) egyes, az anyagba tartozó tételek bizonyítására, az anyagban szereplő algoritmusok helyességének igazolására;
- (K4) a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.
A tantárgyat sikeresen teljesítő hallgató képes lesz:
- (K3) érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;
- (K3) önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;
- (K2) alkalmazni a tárgyban szereplő algoritmusokat;
- (K2) egyes, az anyagba tartozó tételek bizonyítására, az anyagban szereplő algoritmusok helyességének igazolására;
- (K4) a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.
A tárgy oktatói
Telbisz Csanád
doktorandusz
A tantárgy részletes tematikája
1) Gráfelméleti alapfogalmak: gráf, egyszerű gráf, fokszám, részgráf, feszített részgráf, komplementer, élsorozat, séta, körséta, út, kör, izomorfia.
2) Összefüggő gráf, összefüggő komponens. Fa és feszítőfa fogalma, feszítőfa létezése.
3) Gráfok tárolása: szomszédsági mátrix és szomszédsági lista. Irányított gráfok. Gráfelméleti algoritmusok hatékonysága. Az összefüggőség eldöntése, legrövidebb út keresése élsúlyozatlan gráfban: a szélességi bejárás (BFS).
4) Minimális összsúlyú feszítőfa keresése: a Kruskal algoritmus.
5) Euler-séta és -körséta fogalma, ezek létezésének szükséges és elégséges feltétele. Hamilton-út és Hamilton-kör fogalma. Szükséges feltételek ezek létezésére: a k pont törlése után keletkező komponensek maximális száma. Elégséges feltételek: Dirac és Ore tételei.
6) Páros gráfok, karakterizációjuk páratlan körökkel. A kromatikus szám fogalma. Mohó színezés, felső becslés a kromatikus számra a maximális fokszám függvényében. Maximális klikkméret, kapcsolata a kromatikus számmal, Zykov konstrukciója.
7) Intervallumgráfok optimális színezése. Párosítás, lefogó ponthalmaz, független ponthalmaz, lefogó élhalmaz fogalmai. Reláció a maximális párosítás és a minimális lefogó ponthalmaz mérete között. Gallai tételei.
8) Maximális párosítás keresése páros gráfokban, a javító utas algoritmus, annak optimalitása. Kőnig tétele a maximális párosítás és a minimális lefogó ponthalmaz méretének egyenlőségéről.
9) Élkromatikus szám fogalma, reláció a maximális fokszámmal, Vizing tétele, Kőnig tétele páros gráfok optimális élszínezéséről.
10) A maximális folyam feladata: hálózat, folyam és folyam értékének fogalma, a javító utas algoritmus maximális folyam keresésére.Hálózat st-vágásának fogalma, annak kapacitása.
11) Ford-Fulkerson tétel, Edmonds-Karp tétel. Egészértékűségi lemma. Az éldiszjunkt, irányított s-t utak problémája, Menger vonatkozó tétele.
12) Az éldiszjunkt, irányítatlan s-t utak problémája, a pontdiszjunkt s-t utak problémája irányított és irányítatlan esetben is, Menger vonatkozó tételei. Többszörös pont- és élösszefüggőség fogalma, Menger vonatkozó tételei.
13) A legrövidebb utak keresésének problémája valós élsúlyokkal irányított gráfban, a Bellman-Ford algoritmus.
14) Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.
2) Összefüggő gráf, összefüggő komponens. Fa és feszítőfa fogalma, feszítőfa létezése.
3) Gráfok tárolása: szomszédsági mátrix és szomszédsági lista. Irányított gráfok. Gráfelméleti algoritmusok hatékonysága. Az összefüggőség eldöntése, legrövidebb út keresése élsúlyozatlan gráfban: a szélességi bejárás (BFS).
4) Minimális összsúlyú feszítőfa keresése: a Kruskal algoritmus.
5) Euler-séta és -körséta fogalma, ezek létezésének szükséges és elégséges feltétele. Hamilton-út és Hamilton-kör fogalma. Szükséges feltételek ezek létezésére: a k pont törlése után keletkező komponensek maximális száma. Elégséges feltételek: Dirac és Ore tételei.
6) Páros gráfok, karakterizációjuk páratlan körökkel. A kromatikus szám fogalma. Mohó színezés, felső becslés a kromatikus számra a maximális fokszám függvényében. Maximális klikkméret, kapcsolata a kromatikus számmal, Zykov konstrukciója.
7) Intervallumgráfok optimális színezése. Párosítás, lefogó ponthalmaz, független ponthalmaz, lefogó élhalmaz fogalmai. Reláció a maximális párosítás és a minimális lefogó ponthalmaz mérete között. Gallai tételei.
8) Maximális párosítás keresése páros gráfokban, a javító utas algoritmus, annak optimalitása. Kőnig tétele a maximális párosítás és a minimális lefogó ponthalmaz méretének egyenlőségéről.
9) Élkromatikus szám fogalma, reláció a maximális fokszámmal, Vizing tétele, Kőnig tétele páros gráfok optimális élszínezéséről.
10) A maximális folyam feladata: hálózat, folyam és folyam értékének fogalma, a javító utas algoritmus maximális folyam keresésére.Hálózat st-vágásának fogalma, annak kapacitása.
11) Ford-Fulkerson tétel, Edmonds-Karp tétel. Egészértékűségi lemma. Az éldiszjunkt, irányított s-t utak problémája, Menger vonatkozó tétele.
12) Az éldiszjunkt, irányítatlan s-t utak problémája, a pontdiszjunkt s-t utak problémája irányított és irányítatlan esetben is, Menger vonatkozó tételei. Többszörös pont- és élösszefüggőség fogalma, Menger vonatkozó tételei.
13) A legrövidebb utak keresésének problémája valós élsúlyokkal irányított gráfban, a Bellman-Ford algoritmus.
14) Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.