Az előadást kétféleképpen lehet felvenni:
Gyakorlat nélkül (4 kredit): Ekkor az előadást Kombinatorika elemei néven vegyük fel (MBN342E), és NE vegyük fel a gyakorlatot.
Gyakorlattal (6+0 kredit): Ekkor az előadást Kombinatorika néven vegyük fel, és vegyük fel mellé a Kombinatorika gy. gyakorlatot is (MBN341E + MBN341G).
Alapvetően tehát az előadáshoz tartozó gyakorlat opcionális kurzus, de egyes képzési programok tantervei ettől eltérően rendelkeznek (például matematikus szakirányon kötelező a gyakorlat is).
Azok számára, akik felvették a gyakorlatot is, az előadás teljesítésének előfeltétele a gyakorlaton megszerzett aláírás (a gyakorlat követelményrendszere itt olvasható).
Az előadás anyaga egy 50 pontos írásbeli vizsgán lesz számon kérve a vizsgaidőszakban (az ETR-ben meghirdetett időpontokban). A vizsgafeladatsor több feladatot tartalmaz, átfogóan összeválogatva a félév anyagából, és lesz benne egyszerű/mechanikus "gyakorlati feladat" is. A vizsga első része egy beugró, amely az alapdefiníciók és a "tudni kell" tételek/összefüggések ismeretét teszteli. Amennyiben a beugró javításánál komoly hiányosságokra derül fény, az érdemjegy elégtelen, a dolgozat második felének kijavítása nélkül.
Az előadásvizsgán elért pontszámhoz hozzáadódik a gyakorlatról hozott pontszám (a gyakorlaton is legfeljebb 50 pontot lehet szerezni); gyakorlat nélkül
felvett előadás esetén pedig a vizsga pontszáma megkétszereződik. Az így kialakult összpontszám határozza meg az érdemjegyet (ha a korábbi bekezdések
másképp nem rendelkeznek):
0 – 50: elégtelen
51 – 60: elégséges
61 – 70: közepes
71 – 85: jó
86 – 100: jeles
A félév folyamán pluszpontokat is lehet szerezni (legfeljebb 10-et) az előadás alatt tett érdemi hozzászólással/hibajelzéssel, illetve általam kiadott szorgalmi feladatok otthoni megoldásával. A pluszpontok hozzáadódnak a fent kialakult összpontszámhoz.
Az alapfogalmakat/alaptételeket aláhúzás jelöli, ezeket mindenképpen ismerni kell (tétel esetén kimondani). A zölddel jelölt témák nehezebbek / kiegészítő anyagrészek; ezekkel akkor foglalkozzunk, ha az anyag többi része már jól megy (és jó jegyet célzunk meg).
1. Alapok: Bijekciók. A három kombinatorikus alapelv. Egy halmaz elemszámának, végességének precíz definíciója. A kombinatorika alapproblémája.
2. Részhalmazok: Részhalmaz karakterisztikus függvénye, karakterisztikus vektora. Egy halmaz hatványhalmaza.
Egy n elemű halmaz részhalmazainak száma.
3. Binomiális együtthatók: A binomiális együtthatók definíciója. Rekurzió a binomiális együtthatókra. Binomiális tétel. A Pascal-háromszög és alaptulajdonságai. Az (nk) binomiális együttható explicit alakja.
A Pascal-háromszög n-edik sorának négyzetösszege.
4. Formális hatványsorok: A formális hatványsorok és az alapműveletek definíciója. Osztás, kompozíció, gyökvonás, hatványozás. Műveleti tulajdonságok (ezt nem kell betanulni, de számolni tudni kell formális hatványsorokkal). Newton-formula (bizonyítás nélkül).
5. Multihalmazok: Precíz definíció + kapcsolódó alapfogalmak (elemszám, részmultihalmaz stb.). Hatványhalmaz; részmultihalmazok száma. ((nk)) számok definíciója és pontos értéke. Rekurzió az ((nk)) számokra. Az ((nk)) számok generátorfüggvénye.
6. Sorbaállítások: Precíz definíció. n elemű halmaz sorbaállításainak száma. Stirling-formula az n! aszimptotikájára. Inverzióban álló elempár, inverziószám, i(n,k) számok definíciója. Rekurzió az i(n,k) számokra. Az i(n,k) számok generátorfüggvénye. Multihalmaz sorbaállításainak definíciója és száma. Polinomiális tétel.
7. Átrendezések, permutációk: Precíz definíció. n elemű halmaz permutációinak száma. Permutációk szorzása. Ciklusok, [nk] számok. Elsőfajú Stirling-számok. Rekurzió az [nk] számokra. Az [nk] számok és az elsőfajú Stirling-számok generátorfüggvénye.
8. Logikai szita: A szitaformula. Alkalmazások: Fixpont nélküli permutációk száma, szürjektív leképezések száma.
9. Fibonacci-számok: A Fibonacci-számok rekurzív definíciója. A Fibonacci-számok kombinatorikus definíciója, és egy alkalmazás: Fn előállítása binomiális együtthatók összegeként.
A Fibonacci-számok zárt alakja (segédanyag).
10. Lineáris rekurzió: Lineáris rekurzióval definiált sorozatok definíciója, és a zárt alakra hozás menete (konkrét lineáris rekurziókat kell tudni megoldani: 9 kidolgozott mintapélda). A lineáris rekurziók alaptétele.
Középiskolás megközelítés generátorfüggvények nélkül (ez nem tananyag, de vö. alaptétel): itt.
11. Catalan-számok: Rekurzív definíció. Kombinatorikus definíciók (konvex sokszög háromszögeléseinek száma, Dyck-utak száma). A Catalan-számok zárt alakja.
12. Gráfelméleti alapfogalmak: Egyszerű gráf és (általános) gráf fogalma. Fokszám definíciója; a fokszámösszeg és az élszám kapcsolata. Részgráf, feszítő részgráf, feszített részgráf. Séta, vonal, út. Összefüggőség. Reguláris, k-reguláris gráfok.
Egyszerű gráf komplementere.
13. Euler-vonal: Euler-vonal definíciója (zárt és nem zárt is). Euler-tétel + segédtételei.
14. Hamilton-út, Hamilton-kör: Hamilton-út, Hamilton-kör definíciója. Dirac-tétel + segédtételei.
Egy (nem mindig alkalmazható) módszer a Hamilton-kör-mentesség igazolására + analóg állítás Hamilton-útra.
15. Összefüggőség, fák: Elérhetőség ("sétával való összeköthetőség") reláció, komponensek. Fák ekvivalens definíciói (segédanyag). Feszítőfák. Levelek. Ághajtás operáció, fák felépítése ághajtásokkal. A fa éleinek száma.
Gyökeres fák és lerajzolásaik.
16. Csúcsszínezések: Jó színezés, kromatikus szám definíciója. Független ponthalmazok, α(G) paraméter definíciója. χ(G) alsó becslése az α(G) paraméter (és a csúcsszám) segítségével.
Páros gráfok definíciója és karakterizációja. Mohó színezési algoritmus (illusztráció). Kromatikus szám felső becslése a maximális fokszám segítségével, Brooks-tétel (bizonyítás csak a nem reguláris gráfok esetére). Klikk definíciója.
Az ω(G) paraméter, és kapcsolata a kromatikus számmal. Nagy kromatikus számú háromszögmentes gráfok (tananyagon felüli kiegészítés: további konstrukciók).
17. Síkgráfok: Síkgráfok definíciója. A két alappélda nem síkgráfokra. Tartományok. Síkra rajzolt gráf duálisa. Euler-formula és következményei (kiegészítő segédanyag). Térképszínezési probléma, négyszín-tétel kimondása. Hatszín-tétel bizonyítása.
Kuratowski-tétel kimondása.
18. Párosítások: Párosítás, teljes párosítás, ν(G) paraméter definíciója. Kőnig-akadály. Kőnig—Hall-tétel, Kőnig—Frobenius-tétel. Kőnig—Ore-formula. Tutte-akadály. Tutte-tétel (a nehéz irány bizonyítása nélkül).
19. Ramsey-elmélet: Monokromatikus klikkek. Ramsey-tétel. Ramsey-számok. R(3) pontos értéke. R(k) alsó és felső becslése (Erdős Pál tétele).
20. Extremális gráfelmélet: Mantel-tétel. Turán-gráfok (Tn,k). Turán-tétel kimondása (extra: bizonyítás).
Mintavizsga #1, Mintavizsga #2, Mintavizsga #3
A fő segédanyag a korábbi előadó, Hajnal Péter internetes jegyzete a kurzushoz: 2014/2015-ös tanév, 2013/2014-es tanév
Hajnal Péter: Kombinatorikai fogalomtár (nem ehhez a kurzushoz készült, nem fedi le teljesen az anyagot, de sok minden benne van)
Formális hatványsorok műveleti tulajdonságai
Segédanyag a lineáris rekurziók megoldásához: A Fibonacci-számok zárt alakjának levezetése
Kiegészítés a lineáris rekurziók megoldásához: Középiskolás megközelítés + megoldás ellenőrzése (csak a másodrendű esetet tárgyalja, de az alaptétel mindig "megsúgja", hogy milyen alakban kell keresni a megoldást).
Fák ekvivalens definíciói
Az Euler-formula következményei
Euler-vonal: #1 (zárt), #2 (nem zárt).
Hamilton-út: #1, #2. Hamilton-kör: #1, #2, #3, #4.
Fa: #1, #2, #3. Feszítőfa: #1, #2.
Gyökeres fa lerajzolása: #1 (gyökér: 'a'), #2 (gyökér: '1')
Síkgráf duálisa: #1, #2, #3, #4.
A duális gráf az eredeti gráf lerajzolásától is függ: #1.
Gráf jó (csúcs)színezése: #1, #2, #3.
Térképszínezési probléma / négyszíntétel szemléltetése: #1, #2
Párosítás: #1 (nem teljes), #2 (teljes),
#3 (páros gráf egy párosítása), #4 (páros gráf egy A-t lefedő párosítása),
#5 (páros gráf egy teljes párosítása). Kőnig-akadály: #1, #2.
Turán-gráf: #1 (T13,4, T14,4, T13,2 és T14,3), #2 (T7,3).
Hajnal Péter: Összeszámlálási problémák (Polygon Jegyzettár)
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, interneten is olvasható)
Bóna Miklós: Introduction to Enumerative Combinatorics (McGraw-Hill)
Reinhard Diestel: Graph Theory (Springer-Verlag, interneten is olvasható)
Richard P. Stanley: Enumerative Combinatorics (Cambridge University Press)
Hajnal Péter: Elemi kombinatorikai feladatok (Polygon Könyvtár)
Friedl Katalin, Recski András, Simonyi Gábor: Gráfelméleti feladatok (Typotex)
A gyakorlat honlapja
The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"
| ⇦ | Főoldal |
