Kombinatorika időrendi tematika
2013, ősz
A végső tematika az utolsó előadás végén pontosítva lesz.
- Bijekció, párba állító leképezés
- Három kombinatorikus alapelv
- Részhalmazok száma
- k elemű részhalmazok száma
- Polinomok szorzása, binomiális tétel
- ((nk)) számok (k=0,1,2,3,..)
- Sorbaállítások
- Sorbaállítások száma
- Átrendezések, permutációk
- Ciklusok
- Multihalmazok
- Multihalmazok részhalmazai, sorbaállításai
- Szita módszer
- Szita módszer alkalmazásai
- Fibonacci-számok
- Catalan-számok
- Lineáris rekurzió
- Egyszerű gráf, hurokél-nélküli gráf, gráf fogalma
- Fokszám fogalma, fokszámokra vonatkozó egyszerű állítások
- Séta
- Elérhetőség reláció és ennek ekvivalenciareláció volta
- Gráfok komponensei
- Összefüggő gráfok
- Vonal, Euler-vonal fogalma
- Vonal növelései
- Euler-tétel
- Út, kör
- Hamilton-kör, Hamilton-út
- Utak növelése
- Hosszú út keresésére vonatkozó algoritmus;
Dirac-tétel
- Fák; ekvivalens definíciók
- Feszítőfa
- Ághajtás
- Gyökeres fák
- Gráfok színezése
- Mohó színezési algoritmus
- 5-szín-tétel
- Klikkek és kapcsolata a színezéssel
- Párosítások
- Lefogó ponthalmazok
- Kőnig-akadály és kapcsolata a párosításokkal
- Páros gráfokra vonatkozó párosítási tételek
- Turán-gráfok
- Mantel-tétel és bizonyítása
- Turán-tétel kimondása
- R(3)
- Ramsey-számok
- Ramsey-tétel kimondása