Gráfelmélet ea. (informatikus 2005-2007)

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

Tematika:
Gráfok és kódolásuk. Összefüggőség, minimális költségű feszítőfa. Vonalak, kínai portás probléma, Hamilton-körök, utazó ügynök probléma. Párosítások, magyar módszer, Edmonds-algoritmus. Színezések, színezési algoritmusok. Független ponthalmazok, klikkek, Turán-tétel, Ramsey-számok. Gráfproblémák redukciói.

Előfeltétel: