A félév során házi feladatok kerülnek feladásra, amelyek pontértéke és benyújtási határideje a honlapomon lesz közzétéve. A vizsgaidőszakban meghirdetett vizsgaidőpontokban pedig írásbeli vizsgák lesznek (beugróval); melyhez tematika és mintavizsga elérhető lesz a honlapomon. A házi feladatokból és a vizsgából egyaránt legalább az ott elérhető pontszám 40%-át el kell érni (a házi feladatra vonatkozó kritérium a gyakorlati aláírás feltétele). A házi feladatok és vizsga százalékos eredménye 50-50%-os súllyal számít bele a végső érdemjegybe.
0% – 50%: elégtelen
51% – 62%: elégséges
63% – 75%: közepes
76% – 87%: jó
88% – 100%: jeles
A félév folyamán pluszpontokat is lehet gyűjteni órai munkával.
1. Részhalmazok: Kombinatorikus alapelvek. Bijekció.
Egy n elemű halmaz részhalmazainak száma. Részhalmaz karakterisztikus vektora.
2. Binomiális együtthatók: A binomiális együtthatók definíciója. Képlet az (nk) binomiális együtthatóra.
A binomiális együtthatók rekurzív kiszámítási módja. A Pascal-háromszög és alaptulajdonságai (szimmetria, egy sor elemeinek összege). Binomiális tétel.
3. Multihalmazok: Multihalmazok precíz definíciója + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai). Multiplicitásvektor.
Részmultihalmazok száma. Egy n elemű alaphalmaz feletti k elemű multihalmazok száma.
4. Sorbaállítások, átrendezések: Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma.
Multihalmaz sorbaállítása, és a sorbaállítások száma.
Átrendezések (permutációk) definíciója. Egy n elemű halmaz átrendezéseinek száma. Minden permutáció ciklusokra bomlik.
5. Logikai szita: A szita formula + egy tetszőleges alkalmazás (3-nál több kiszitálandó halmazzal).
6. Rekurziók:
Lineáris rekurziók és megoldásuk.
Lineáris rekurziók alaptétele (biz. nélkül).
Fibonacci-számok rekurzív definíciója. Fibonacci-számok zárt alakja. Kiegészítés (nem vizsgaanyag): Rekurziók a kombinatorikában.
7. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója. Fokszámok. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata).
Részgráf. Feszítő és feszített részgráfok. Séta, vonal, út. Kör. Teljes gráf.
Egyszerű gráf komplementere. Gráfok izomorfiája.
8. Euler-vonal: Euler-vonal definíciója (nyílt és zárt). Euler-tétel.
A történelmi példa: Königsberg (ma Kalinyingrád) térképe Euler idejében, és a gráf.
9. Hamilton-út, Hamilton-kör: Hamilton-út, Hamilton-kör definíciója.
Dirac-tétel (bizonyítás nélkül).
10. Összefüggőség, fák: Összefüggőség. "Sétával való összekötöttség" reláció, komponensek.
Fák ekvivalens definíciói (hasznos minél többet ismerni, de elég annyi, amennyi előadáson volt).
Feszítőfák összefüggő gráfokban. Levelek. Ághajtás operáció, fák "struktúratétele" (fák jellemzése ághajtás operációkkal). A fa éleinek száma.
11. Páros gráfok: Páros gráfok definíciója és jellemzésük páratlan körökkel (csak az egyszerű irányt gondoltuk végig). A páros gráfok és a csúcsszínezések kapcsolata.
Fokszámösszeg a két színosztályban.
12. Csúcsszínezések: Jó színezés és kromatikus szám. Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata.
1. feladatsor
2. feladatsor
3. feladatsor
4. feladatsor
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR
A fő segédanyag Hajnal Péter internetes jegyzete a kurzushoz: 2016/2017-es tanév, 2013/2014-es tanév
Ez a jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2016/2017-es tanév
Euler-vonal: #1 (zárt),
#2 (zárt),
#3 (nyílt).
Hamilton-út: #1, #2.
Hamilton-kör: #1, #2, #3.
Komponensek: #1 (gráf 4 komponenssel),
#2 (gráf 3 komponenssel),
#3 (gráf 3 komponenssel).
Fa: #1, #2.
Feszítőfa: #1.
Gyökeres fa lerajzolása: #1 (gyökér: 'r'), #2 (gyökér: 'a').
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.
Jó (csúcs)színezés: #1, #2.
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. Lefogó ponthalmaz: #1.
Turán-gráf: #1 (T13,4, T14,4, T13,2 és T14,3), #2 (T7,3).
A képek többségét más oldalakról linkeltem (az URL-ből kiolvasható/megkereshető a forrás).
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, ingyenesen olvasható az interneten)
Bóna Miklós: Introduction to Enumerative Combinatorics (McGraw-Hill)
Reinhard Diestel: Graph Theory (Springer-Verlag, ingyenesen olvasható az interneten)
Richard P. Stanley: Enumerative Combinatorics, Vol. 1-2 (Cambridge University Press)
Benny Sudakov: Graph Theory (internetes jegyzet)
The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"
