BSc Matematika Alapszak
Tantárgyleírás
2013.
Borromeo gyűrűk
Véges matematika1 — normál változat
Óraszám
ea/gy		 Kredit
ea/gy		 Számonkérés Szakirány Tárgykód
ea/gy		 Ajánlott
félév		 Státusz
2 + 2 2 + 3 kollokvium +
gyak. jegy		 közös mm1c1vm1
mm1c2vm1		 1 kötelező
tanári minor mm1c1vm1
mm1c2vm1		 3 kötelező
Erős Gyenge előfeltételek
Előadás
Gyenge:
a gyakorlat
Megjegyzések
  • A Véges matematika1 normál, haladó és intenzív változata egymás között átjárható.
  • Pótlási lehetőség: Egy sikertelen zárthelyi pótolható.
A tematikát kidolgozta:
Szükséges előismeretek
A középiskolai matematika anyag.
A tantárgy célkitűzése
A ma már középiskolában, sőt általános iskolában is egyre többször előforduló kombinatorikus gondolkodásmód kialakítása sok feladat-megoldással.
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
  • Stratégiás játékok.
  • 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. Átlagolás.
  • 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.
  • A Ramsey tétel néhány speciális esete, két és több szín esetére (csak gyakorlaton). Extremális gráfok: maximális élszám háromszögmentes gráfokra.
↻