Tárgy kód és cím

Tárgy kód és cím
MGE05 Gráfelmélet (= M365 Kombinatorika II.)
Meghirdetés
Õszi félévekben 2+0 bontásban.
Hallgatóság
Matematika tanárszakos hallgatóknak Geometria blokktárgy.
A kurzus célja
A gráfelmélet alapfogalmainak, alaptechnikáinak bemutatása.
Tematika
Gráfelméleti alapfogalmak: gráf, egyszerû gráf, irányított gráf, izomorfizmus, fokszám, fokszámsorozat. Gráfok összefüggõsége, fák, feszítõfák. Euler-vonal, Hamilton-kör. Párosítások páros gráfokban: Kõnig-tétel, Magyar módszer. Gráfok színezései: a kromatikus szám és a legnagyobb fokszám kapcsolata, a kromatikus szám és a legnagyobb klikk mérete közötti kapcsolat, mohó színezési algoritmus. Turán-elmélet: Turán-tétel és alkalmazásai. Ramsey-elmélet: Ramsey-tétele és számelméleti, geometriai alkalmazásai. Síkgráfok, perfekt gráfok.
Irodalom
Hajnal Péter: Gráfelmélet, Polygon jegyzet, Szeged, 1997.

Gráfelméleti alapfogalmak: gráf, egyszerû gráf, irányított gráf, izomorfizmus, fokszám, fokszámsorozat. Gráfok összefüggõsége, fák, feszítõfák. Euler-vonal, Hamilton-kör. Párosítások páros gráfokban: Kõnig-tétel, Magyar módszer. Gráfok színezései: a kromatikus szám és a legnagyobb fokszám kapcsolata, a kromatikus szám és a legnagyobb klikk mérete közötti kapcsolat, mohó színezési algoritmus. Turán-elmélet: Turán-tétel és alkalmazásai. Ramsey-elmélet: Ramsey-tétele és számelméleti, geometriai alkalmazásai. Síkgráfok, perfekt gráfok.