• 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 3.

• ``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 10.

• 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

TUDNI KELL Binomiális tétel Multihalmaz (elemszám, részmultihalmaz) ((nk)) számok definíciója TUDNI ILLIK ((nk)) számok rekurziója

Szeptember 17.

• Formális hatványsorok: alapműveletek
• Sorbaállítások, faktoriális függvény
• Sorbaállított részhalmazok: Formula a binomiális együtthatókra
• Inverziók

TUDNI KELL Formális hatványsorokra vonatkozó alapműveletek definíciója Egy halmaz sorbállításának fogalma n! definíciója [n] egy sorbállítása esetén inverzióban álló elempár fogalma TUDNI ILLIK ((nk)) számok generátorfüggvénye (rk) számok, ahol r valós szám Beszúrás operáció sorbaállított halmazokra

Szeptember 24.

• Á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
• Multihalmazok sorbaállításai

TUDNI KELL Egy halmaz átrendezésének/permutációjának fogalma Egy permutáció ciklusai [nk] számok fogalma Egy multihalmaz sorbállításának fogalma TUDNI ILLIK [n] k inverziójú sorbaállítasainak számára vonatkozó rekurzió [n] k inverziójú sorbaállítasainak számait összefüző polinom 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) Multihalmaz sorbaállításainak száma Multinomiális tétel

Október 1.

• Osztályozások
• Osztályozások k osztállyal
• Megfordítási képletek

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

Október 8.

• Logikai szita (tartalmazás és kizárás elve)
• Logika szita: alkalmazások
• Generátorfüggvények módszere
• Lineáris rekurzió, Fibonnacci-számok

TUDNI KELL A logikai szita képlete Fibonacci-számok definíciója Lineáris rekurzióval definiált sorozat definíciója TUDNI ILLIK A logikai szita alkalmazása 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

Október 15.

• Lineáris rekurziókra vonatkozó alaptétel, példák
• Catalan-számok
• Formális hatványsorok II: racionális kitevőjű hatványozás, Newton-formula
• Catalan-számok elemi tárgyalása

TUDNI KELL Lineáris rekurzióval definiált sorozat generátorfüggvényének felírása és abból együtthatóinak kiolvasása. Catalan-számok definíciója TUDNI ILLIK Catalan-számok rekurziója (Segner-tétel) Catalan-számok gnerátorfüggvénye 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

Október 22.

• Gráfelméleti alapfogalmak
• Séta, vonal, út
• Összefüggőség, komponensek

TUDNI KELL Egyszerű gráf, gráf fogalma Egy csúcs fokszámának definíciója 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 gráfban a fokok összegére vonatkozó formula és bizonyítása 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

Október 29.

• Euler-vonal, záródó Euler-vonal
• Hosszú utakat, köröket kereső algoritmusok, Dirac-tétel
• Minimális összefüggő gráfok: 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 12.

• Gyökeres fák
• Színezések alapfogalmai
• Mohó színezési algoritmus
• Klikkek mérete és a kromatikus szám kapcsolata

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 19.

• 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

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 26.

• Párosítások: Alapfogalmak
• Párosítások
• Turán-tétel

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 3.

• 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.