Gráfelmélet és alkalmazásai ea. (OT 2022)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
Gráfok fogalma, fokszám fogalma, példák. Sétálás gráfokban. Összefüggőség. Vonalak. Euler-vonal, Euler tétele. Utak, körök, Hamilton-út, Hamilton-kör. Dirac tétele. Gráfok komponensei, fák. Gráfok színezései. Páros gráfok. Mohó színezések. Térkép színezési probléma. Gráfok nagy kromatikus számmal, de nagy klikkek nélkül. Síkgráfok fogalma. Példák nem síkgráfokra. Kuratowski tételének kimondása. Hat-szín-tétel. Párosítások gráfokban. Gráfok lefogása. Kőnig-tétel. A Tutte-akadály fogalma és Tutte-tétel kimondása.

Előfeltétel: nincs.

Helyettesítő tárgyak: nincsenek.

Előadás:
Kurzuskód: MTNM842E Kredit: 3 Óraszám: 1 hetente