Kombinatorika időrendi tematika
2014, ő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 alapelv
- Részhalmazok száma
- k elemű részhalmazok száma
- Polinomok szorzása, binomiális tétel
- Sorbaállítások
- Sorbaállítások száma
- Inverziók
- k inverzióval rendelkező sorbaállítások
- Átrendezések, permutációk
- Ciklusok
- k ciklussal rendelkező permutációk száma
- Multihalmazok
- Multihalmazok részhalmazai, sorbaállításai
- Formális hatványsorok és alapműveleteik
- ((nk)) számok (k=0,1,2,3,..) generátorfüggvénye
- Szita módszer
- Szita módszer alkalmazásai
- Generátorfüggvény módszer: Fibonacci-számok
- Generátorfüggvény módszer: 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
- Csúcsok és élek elhagyása gráfokból, feszített részgráf, részgráf
- 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
- Két-színezhető gráfok jellemzése
- Mohó színezési algoritmus
- Alkalmazások: síkgráfok színezése
- Klikkek és kapcsolata a színezéssel
- Példa háromszög nélküli, nagy kromatikus számú gráfokra
- 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
- Független ponthalmaz, klikkek, komplementer gráf
- Mantel-tétel és bizonyítása
- Turán-gráfok
- Turán-tétel kimondása
- Mantel tételének bizonyítása
- Ramsey-tétel
- Ramsey-számok
- R(3) Ramsey-szám meghatározása