Matematikatanári szak
Tantárgyleírás
2016.
Borromeo gyűrűk
Véges matematika1-tk
Óraszám
ea/gy		 Kredit
ea/gy		 Számonkérés Modul Tárgykód
ea/gy		 Ajánlott
félév		 Státusz
2 + 2 5 + 0 kollokvium +
aláírás		 közös képzés mm5t1vm1
mm5t2vm1		 1 kötelező
Irodalom
  • Elekes György: Kombinatorika feladatgyűjtemény. ELTE jegyzet.
  • Hajnal Péter: Elemi kombinatorikai feladatok. JATE Polygon Kiadó.
  • Lovász László, Pelikán József, Vesztergombi Katalin: Diszkrét matematika. TypoTeX, 2006.
Tematika
  • Leszámlálási alapfeladatok: permutációk, variációk, kombinációk ismétlés nélkül és ismétléssel. Alapötletek leszámlálási feladatok megoldására: egymás utáni döntések, „Dobjuk ki a rosszat” elv alkalmazásai. A többszöri megszámlálás korrekciója („tehén-szabály”). Logikai szitaformula és változatai, mint a „Dobjuk ki a rosszat” elv általánosítása. Rekurziós okoskodások, Fibonacci-számok, ezekre vezető kombinatorikai feladatok. A skatulyaelv és alkalmazásai kombinatorikai és geometriai feladatokban.
  • Binomiális együtthatók, azonosságok binomiális együtthatókra. Kitalálós játékok: a Barkochba és változatai, hamis pénz kitalálása. Módszerek lehetetlenség igazolására: színezések, számozások.
  • Gráfok fogalma, hurokél, többszörös él, egyszerű gráfok. Pontok fokszáma és élek száma közti összefüggés, és alkalmazásai. Egy speciális eset:páros gráfok, a fokszám-összefüggés páros gráfokra. Részgráfok, feszített részgráfok. Séták, vonalak, utak, körök és kapcsolatuk. Összefüggő és nem összefüggő gráfok: komponensek (a „komponenstétel”). Fák és erdők, élszámuk meghatározása. A „königsbergi hidak problémája”: Euler-vonal ill. körvonal létezésének szükséges és elégséges feltétele. Irányított gráfok, turnamentek. Az Euler-tétel megfelelője irányított gráfokra (biz. nélkül). Hamilton-körök és Hamilton-utak, szükséges feltétel létezésükre. Elégséges feltétel(ek) Hamilton-körök és Hamilton-utak létezésére (biz. nélk.) összefüggőségi és útkereső algoritmusok: részletesen csak a szélességi bejárás. Síkgráfok, Euler-formula (biz. nélk.), Kuratowski tétele (biz. nélk.). Síkgráfok élszáma. Gráfszínezések, kromatikus szám: kapcsolat a maximális fokszámmal és a legnagyobb teljes részgráf méretével. Síkgráfok színezése: a hatszíntétel.
↻