|
Tárgy kód
és cím
|
|
M
265 Kombinatorika I.
|
|
Meghirdetés
|
|
A
õszi félévben 3+2 bontásban kerül meghirdetésre.
|
|
Hallgatóság
|
|
A
kurzus a matematikus képzés 1. félévében
és a matematika szak választható blokkjában
szerepel.
|
|
A kurzus célja
|
|
A
gráfelmélet és halmazrendszerek alapfogalmainak, alaptechnikáinak
bemutatása.
|
|
Tematika
|
|
Gráfelmélet:
Gráfok összefüggõsége, Komponensek, Fák,
Irányított gráfok összefüggõsége,
Erõsen összefüggõ gráfok , Kétszeresen
élösszefüggõ gráfok, Kétszeresen
összefüggõ gráfok, k -szorosan élösszefüggõ
és összefüggõ gráfok, Menger tételei,
Párosítások, Kõnig-tétel, Hall-tétel,
Frobenius-tétel, Tutte-tétel, Berge-formula, Párosítási
algoritmusok, Euler-gráfok, Kínai postás problémája,
Hamilton-körök, Utazó ügynök problémája,
Gráfok színezése, Brooks-tétel, Gráfok
kromatikus száma és a klikkek méretének kapcsolata,
Gráfok élszínezése, Ramsey-tétel és
alkalmazásai, Turán-tétel és alkalmazásai,
Síkgráfok, síkra rajzolt gráfok, Euler-tétel,
Kuratowski-tétel, Perfekt gráfok, példák, Perfekt
gráf-tétel, Intervallum gráfok.
Halmazrendszerek: Extremális halmazrendszerek, Blokkrendszerek, Véges geometriák, Hadamard-mátrixok, Optimalizálási kérdések |
|
Irodalom
|
|
R.
Stanley, Enumerative Combinatorics, Wadswarth&Brooks/Cole, 1985., N.J.
Vilenkin, Kombinatorika, Mûszaki Könyvkiadó, 1971., B.
Bollobás, Combinatorics, Cambridge University Press, 1986., Hajnal
Péter: Kombinatorika feladatok matematikus hallgatók számára,
JATE jegyzet.
Hajnal Péter: Gráfelmélet, Polygon jegyzet, Szeged, 1997. |