• Amit a kurzusról tudni kell
• Amit a vizsgáról tudni kell
• Tematika időrendben és súlyozva
• Mintavizsga kérdések
• Mit ne csináljunk a vizsgán

Szeptember 6.

• ``Számtan''
• Az alapprobléma
• Részhalmazok száma
• k-elemű részhalmazok
• Előadáson nem szerepelt, nem vizsgaanyag. De jó tudni: Binomiális együtthatók paritása
• Polinomok

TUDNI KELL Párbaállító leképezések/bijeciók Kombinatorikus alapelvek Részhalmazok karakterisztikusvektora/függvénye (nk) számok definíciója TUDNI ILLIK H részhalmazai és az n hosszú 0-1 vektorok közötti párbaállítás (n=|H|) (nk) számok/Pascal-háromszög rekurziója

Szeptember 13.

• Binomiális tétel
• Előadáson nem szerepelt, nem vizsgaanyag. De jó tudni: [n] halmaz k elemű részhalmazainak statisztikája az elemeik összegének paritása szerint
• Multihalmazok, multihalmazok részmultihalmazai
• Halmaz feletti k elemű multihalmazok
• Formális hatványsorok: alapműveletek

TUDNI KELL Binomiális tétel Multihalmaz (elemszám, részmultihalmaz) ((nk)) számok definíciója Formális hatványsorokra vonatkozó alapműveletek definíciója TUDNI ILLIK ((nk)) számok rekurziója ((nk)) számok generátorfüggvénye (rk) számok, ahol r valós szám

Szeptember 20.

• Sorbaállítások, faktoriális függvény
• Sorbaállított részhalmazok: Formula a binomiális együtthatókra
• Multihalmazok sorbaállításai
• Inverziók

TUDNI KELL Egy halmaz sorbállításának fogalma n! definíciója Egy multihalmaz sorbállításának fogalma [n] egy sorbállítása esetén inverzióban álló elempár fogalma TUDNI ILLIK Beszúrás operáció sorbaállított halmazokra Multihalmaz sorbaállításainak száma Multinomiális tétel [n] k inverziójú sorbaállítasainak számára vonatkozó rekurzió [n] k inverziójú sorbaállítasainak számait összefüző polinom

Szeptember 27.

• Átrendezések/permutációk, körökbe állítások
• Előadáson nem szerepelt, nem vizsgaanyag. De jó tudni: Páros és páratlan permutációk
• Átrendezések k ciklussal

TUDNI KELL Egy halmaz átrendezésének/permutációjának fogalma Egy permutáció ciklusai [nk] számok fogalma TUDNI ILLIK Beszúras operáció átrendezések/permutációk esetén [nk] számokra vonatkozó rekurzió [nk] számokat összefűző polinom leírása (n fix)

Október 4.

• Osztályozások
• Osztályozások k osztállyal
• Megfordítási képletek
• Logikai szita (tartalmazás és kizárás elve)
• Logika szita: alkalmazások

TUDNI KELL Egy halmaz osztályozásának fogalma {nk} számok definíciója A logikai szita képlete TUDNI ILLIK {nk} számokra vonatkozó rekurzió {nk} számok (n fix) összefűzése az x(x-1)...(x-k+1) polinomokkal A logikai szita alkalmazása

Október 11.

• Generátorfüggvények módszere
• Lineáris rekurzió, Fibonnacci-számok
• Lineáris rekurziókra vonatkozó alaptétel, példák
• Catalan-számok

TUDNI KELL Fibonacci-számok definíciója Lineáris rekurzióval definiált sorozat definíciója Catalan-számok definíciója TUDNI ILLIK Lineáris rekurzióval felírt sorozatok (példaul Fibonacci-számok) generátorfüggvényének kiszámítása Algebrai törtfüggvények parciális törtekre bontása és a megfelelő generátorfüggvény együtthatóinak kiolvasása Catalan-számok rekurziója (Segner-tétel) Catalan-számok gnerátorfüggvénye

Október 17.

• Formális hatványsorok II: racionális kitevőjű hatványozás, Newton-formula
• Catalan-számok elemi tárgyalása
• Gráfelméleti alapfogalmak

TUDNI KELL Egyszerű gráf, gráf fogalma Egy csúcs fokszámának definíciója TUDNI ILLIK Newton-formula, binomiális formula kiterjesztése racionális kitevőkre Az együtthatók kiolvasása a Catalan-számok generátorfüggvényéből a Newton-képlet segítségével Catalan-számok alternatív leírásai Egy gráfban a fokok összegére vonatkozó formula és bizonyítása

Október 24.

• Séta, vonal, út
• Összefüggőség, komponensek
• Euler-vonal, záródó Euler-vonal

TUDNI KELL Séta fogalma, sétálás, záródó séta Elérhetőség reláció Összefüggő gráf fogalma Élelhagyás, csúcselhagyás fogalma Részgráf, feszített részgráf Egy gráf komponenseinek fogalma Vonal fogalma, Mohó vonalnövelés Euler-vonal fogalma TUDNI ILLIK Egy vonal által bejárt részgráf fokaira vonatkozó tétel Mohó vonalnövelés elakadásának helyére vonatkozó tétel Euler-tétel kimondása és az egyszerű irány azonosítása, indoklása

November 1.: Ünnep, Mindenszentek napja

November 8.

• Hosszú utakat, köröket kereső algoritmusok, Dirac-tétel
• Minimális összefüggő gráfok: fák
• Gyökeres fák

TUDNI KELL Út fogalma, Hamilton-út fogalma Kör fogalma, Hamilton-kör fogalma Mohó útnövelés Fa fogalma Feszítő fa fogalma Ághajtás operáció, ághajtásokkal felépíthető gráfok Gyökeres fa, gyökeres fa generációi TUDNI ILLIK Út csavarása, csavarat utak tulajdonságai Csavarásos növelés garantált, ha minden pontnak legalább |V|/2 szomszédja van Hamilton-út csavarásos bezárása garantált, ha minden pontnak legalább |V|/2 szomszédja van A fa fogalmának alternatív leírásai Ághajtásokkal felépíthető gráfok és fák kapcsolata Fák élszáma és csúcsszáma közötti kapcsolat

November 15.

• Színezések alapfogalmai
• Mohó színezési algoritmus

TUDNI KELL Gráf (csúcs)színezése, jó színezés Gráf kromatikus száma Mohó színezési algoritmus Gráf szép lerajzolása Síkgráf fogalma TUDNI ILLIK 2-színezhető gráfok jellemzése A mohó színezés színigénye és a maximális fok kapcsolata

November 22.

• Síkgráfok színezései, Négy-szín-sejtés/négy-szín-tétel
• Javításos színezési algoritmusok
• Klikkek mérete és a kromatikus szám kapcsolata

TUDNI KELL Térkép színezési probléma, négy-szín-tétel Klikk fogalma és a hozzá kapcsolódó optimalizálási probléma Párosítás fogalma és az ehhez kapcsolódó optimalizálási kérdés TUDNI ILLIK Példák nem síkgráfokra Síkrarajzolt gráfok duálisa/térkép színezési probléma két formája Kempe-átszínezés Klikkek és a színezési probléma kapcsolata Vannak háromszög nélküli magas kromatikus számú gráfok

November 29.

• Párosítások: Alapfogalmak
• Párosítások

TUDNI KELL Kőnig-akadály TUDNI ILLIK Mit akadályoz meg egy Kőnig-akadály és miért Mit mond egy Kőnig-akadály egy tetszőleges párosítás méretéről Kőnig tétele Kőnig-Ore-formula Kőnig-Hall-tétel Kőnig-Frobenius-tétel Tutte-akadály

December 6.

• Turán-tétel
• Ramsey-tétel

    Ha az előadással, gyakorlattal kapcsolatban bármilyen kérdés, megjegyzés, vélemény stb. felmerül, akkor azokat az hajnal@math.u-szeged.hu email címen érdeklődve várom.