Kombinatorika súlyozott tematika
2017 ősz
Az alábbi szabályok nem kőbe vésett szabályok, de jó
szem előtt tartani a vizsgánál készülésnél. Az
alapok utáni listám nem sorolja be a teljes tematikát, de egy
érzést ad milyen mélységű tudásra milyen jegyet lehet remélni.
Alapfogalmak
Bijekció
(nk) számok
Binomiális tétel
Sorbaállítások
Inverzióban álló számpárok
Átrendezések, permutáció
Ciklus
Fibonacci-számok
Lineáris rekurzió
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
Kőnig-akadály
Független ponthalmaz, alfa paraméter
Turán-gráfok
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
Nagy homogén halmazt kereső algoritmus
A fentieket tudni kell. Ezekben tapasztalt hiány, elégtelen vizsgát jelent.
Sajnos csak ezek tudása viszont nem biztos, hogy elégséges
jegyet eredményez. Sokan azt hiszik, hogy ezeket megtanulták, de írásbeli
visszaadásuk hiányokat, értelmetlenségeket, elírásokat
tartalmaz. A fentiekre akkor építhet valaki egy átmenő vizsgát,
ha többet is lát az anyagból
(azt esetleg nem feltétlen teljes mélységben) és
ideje volt "megemészteni a fogalmakat".
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.
(nk) 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ó
i(n,k) számokra vonatkozó rekurzió
n elem k ciklusú permutációinak számára vonatkozó rekurzió
Szita formula egy alkalmazása
Lineáris rekurzióval definiált sorozat generátorfüggvényének
felírása
Lineáris rekurzióval definiált sorozat generátorfüggvényéből
a sorozatot leíró formula "kiolvasá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)
Mit mond egy Kőnig-akadály a legnagyobb párosítás méretéről (indoklás)
Turán-gráfok és n pontú, k elemű klikk nélküli gráfok élszáma
közti viszony (kimondás)
Ramsey-számok (definíció)
A fentiek alapos tudása biztos közepes jegy. Átmenő jegy
megszerzéséhez is ajánlott ezeknek az összefüggéseknek a megértése.
A többi része az anyagnak négyes, ötös érdemjegy megszerzéséhez
szolgálhatnak. Például
Szita formula bizonyítása
Ramsey-tétel bizonyítása
Hat-szín-tétel bizonyítása
Mantel-tétel bizonyítása