Kombinatorika súlyozott tematika

2011, ő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
  • Javító út
  • 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
  • Mohó párosítás 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
  • 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)
  • Javító út létezése mit mond a párosításról (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

  • n elem k ciklusú permutációinak számának generátorfüggvénye
  • Szita formula bizonyítása
  • Catalan-számokra vonatkozó formula
  • Ramsey-tétel bizonyítása
  • Öt-szín-tétel bizonyítása
  • Mantel-tétel bizonyítása