Kombinatorika súlyozott tematika

2019

Az alapok fontosak. Ezzel kezdjük a tanulást. Értsük meg ezeket a fogalmakat.

Alapfogalmak

Bijekció
(ⁿ_k) számok
Binomiális tétel
Sorbaállítások
Átrendezések, permutáció
Ciklus [H->H bijekció/permutáció felfogható jobb szomszédságnak, ami egy körökbe állítás. A körök a permutáció ciklusai.]
Fibonacci-számok
Lineáris rekurzió [olvasmány!]
Szita formulá kimondása
Egyszerû gráf, hurokél-nélküli gráf, gráf fogalma
Fokszám fogalma
Séta
Elérhetõség reláció
Csúcsok elhagyása gráfokból, feszített részgráf
Gráfok komponensei
Összefüggõ gráf
Vonal, Euler-vonal fogalma
Élek elhagyása gráfokból, feszítõ részgráf
Út, kör
Fa
Feszítõfa
Gyökeres fa
Hamilton-kör, Hamilton-út
Gráfok színezése, kromatikus szám
Klikk, omega paraméter
Párosítások, nü paraméter
Lefogó ponthalmazok, tau paraméter

Alapalgoritmusok

Minimális, az összes pontot tartalmazó, összefüggõ részgráf keresése összefüggõ gráfokban
Vonal növelései
Út mohó növelése, csavarása
Mohó színezési algoritmus

Alapösszefüggések

Ezek indoklása egy-két mondatban elmondhatók. Sokszor egy mélyebb összefüggés úgy mond triviális iránya.

(ⁿ_k) számok/Pascal-háromszög rekurziója
Binomiális tétel indoklása
n elemû halmaz feletti k elemû multihalmazok számára vonatkozó formula bizonyítása
Sorbaállítások számára vonatkozó rekurzió
Permutációk számára vonatkozó rekurzió
Szita formula egy alkalmazása
Fokszámokra vonatkozó egyszerû állítások (indoklás)
Elérhetõség reláció ekvivalenciareláció volta (indoklás)
Euler-tétel kimondása
Fák ekvivalens definíciói (kimondás)
Két-színezhetõ gráfok jellemzése (kimondás)
Mohó színezési algoritmus outputjának mérete és a maximális fokszám viszonya (indoklás)
Kromatikus szám és az omega paraméter viszonya (indoklás)
nü és tau paraméterek viszonya (indoklás)
Mit akadályoz meg egy Kõnig-akadály (indoklás)
Turán tétele (kimondás)
6 elemû társaságra vonatkozó feladat és megoldása
Ramsey-számok (definíció)

Mélyebb összefüggések

Ezek megtanulása akkor ajánlott, ha a többi anyagrész már biztosan tudott.