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