Gráfelmélet elemei

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

Tematika:
Gráfelméleti alapfogalmak. Összefüggőség, fák, komponenesek. Séta, vonal, út, Euler-vonal, Hamilton-kör, Dirac-tétel. Irányított gráfok. Kétszeresen összefüggő gráfok, fülfelbontások. Párosítások, Kőnig-tétel, magyar módszer. Színezések, kromatikus szám, mohó színezések, Brooks-tétel, Kempe-láncok, síkgráfok színezése. Független ponthalmazok, klikkek, mohó algoritmus független ponthalmaz keresése, Turán-tétel, extremális gráfelmélet, Ramsey-tétel, alkalmazások.

Előfeltétel: nincs.

Helyettesítő tárgyak: nincsenek.

Előadás:
Kurzuskód: Mm1403 Kredit: 3 Óraszám: 2 hetente