Hétfő 12:00-14:00, Grünwald terem online kurzus (ld. CooSpace)
Az előadás teljesítésének előfeltétele a teljesített gyakorlat (melynek részletes feltételrendszere a gyakorlat honlapján olvasható). Az előadásvizsgán maximum 40 pont szerezhető.
Az előadásvizsga egy rövid írásbeli beugróval kezdődik, mely átfogó módon teszteli a tananyag fogalmainak és tételeinek
ismeretét (bizonyítások nélkül), akár példákon keresztül. Amennyiben a beugróban komoly hiányosságokra derül fény, az érdemjegy szóbeli vizsga nélkül
elégtelen. A beugró után egy tételhúzásos szóbeli vizsga következik: A hallgató egy kombinatorika és egy gráfelmélet tételt ismertet szóban,
írásbeli felkészülés után. (A tételhúzás után kijelölöm, hogy mely részeket kell majd jobban részletezni, és melyeket elegendő kevésbé.)
A 40 pontból legalább 15 pontot el kell érni a kurzus teljesítéséhez (alapvető hiányosságok 0 pontot eredményeznek).
E feltétel teljesülése esetén a vizsgán megszerzett pontszámhoz hozzáadódik a gyakorlatról hozott pontszám (legfeljebb 60 pont), és kialakul az érdemjegy:
0 – 50: elégtelen
51 – 62: elégséges
63 – 75: közepes
76 – 87: jó
88 – 100: jeles
A félév folyamán pluszpontokat is lehet gyűjteni az előadás alatt tett érdemi hozzászólással/hibajelzéssel. A pluszpontok hozzáadódnak a fent kialakult összpontszámhoz. Továbbá a tételsorban szerepelnek olyan elemek is, amelyek ismerete pluszpontokat jelent a szóbeli vizsgán. A megváltozott követelményrendszer a CooSpace hirdetőtáblán olvasható.
A zöld szín a nehezebb anyagrészeket jelöli, ezeket csak a jeles érdemjegyet megcélzó hallgatóktól kérdezhetem (a beugróban biztosan nem fognak szerepelni).
A barna színű részek nem tartoznak a vizsgaanyaghoz: ha a törzsanyag jól ment (!),
akkor ezen kiegészítő részek ismerete pluszpontot ér (a SZORGALMI címkéjűek többet; a "pluszpontért"
részek kevesebbet; az egyebek inkább csak olvasmányok).
1. Alapok: A kombinatorika három alapelve. Bijekció.
Skatulyaelv (példával, pl. gyakorlatról), általánosított skatulyaelv. Kettős leszámlálás (példával, ld. későbbi előadások / gyakorlat).
Részhalmaz karakterisztikus függvénye és karakterisztikus vektora. Hatványhalmaz. Egy n elemű halmaz részhalmazainak száma.
Páros/páratlan elemszámú részhalmazok száma (ld. 1. gyakorlat, vagy II. pont itt).
2. Binomiális együtthatók: A binomiális együtthatók definíciója. A binomiális együtthatók rekurzív kiszámítási módja.
A Pascal-háromszög és alaptulajdonságai (szimmetria, egy sor elemeinek összege). Képlet az (nk) binomiális együtthatóra.
Binomiális tétel.
SZORGALMI: Páros/páratlan elemösszegű k elemű részhalmazok (9. oldal, 4. feladat).
3. Polinomok, formális hatványsorok: Formális hatványsorok és polinomok definíciója, generátorfüggvények. Alapműveletek (összeadás és szorzás). Formális hatványsorok műveleti tulajdonságai (nem kell betanulni; számolni kell tudni formális hatványsorokkal), többtényezős szorzat.
Formális hatványsor fokszáma, osztás, egész kitevős hatványozás.
Az 1/(1-x) formális hatványsor. Deriválás. Kompozíció.
Az 1/(1-x)2 formális hatványsor.
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása
(az általános elméletet nem fogom kérdezni, konkrét polinom/polinom alakú hatványsor együtthatóit tudjuk kiszámolni lineáris rekurzió megoldásakor).
Trinomiális és multinomiális tétel.
SZORGALMI: n-edik gyök, tört kitevőjű hatványok, Newton-formula (ld. Formális hatványsorok prezentáció vége).
4. Multihalmazok: Multihalmazok precíz definíciója + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai). Multiplicitásvektor.
Részmultihalmazok száma. Az ((nk)) számok definíciója. Rekurzió az ((nk)) számokra.
((nk)) mint bizonyos vektorok száma.
Az ((nk)) számok pontos értéke. Az ((nk)) számok generátorfüggvénye.
5. Sorbaállítások, átrendezések: Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma. Stirling-formula (biz. nélkül). Inverzióban álló elempár. Inverziószám definíciója és gyors kiszámítási módja.
Az inverziószám gyors kiszámításánál látott bijekció Sn és {0,...,n-1}×...×{0,1}×{0} között.
Az i(n,k) számok definíciója és generátorfüggvénye.
Multihalmaz sorbaállításai, és a sorbaállítások száma.
Bijekciók száma két n elemű halmaz között. Átrendezések (permutációk) definíciója. Az átrendezések és a sorbaállítások kapcsolata.
Egy n elemű halmaz átrendezéseinek száma.
Ciklusok. Minden permutáció ciklusokra bomlik.
SZORGALMI: Páros és páratlan permutációk (vö. Diszkrét matematika kurzus).
6. Logikai szita: A szita formula. Alkalmazások: Fixpont nélküli permutációk száma, szürjektív leképezések száma.
7. Rekurziók: Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni).
Fibonacci-számok rekurzív definíciója. Lineáris rekurziók, és megoldásuk generátorfüggvény-módszerrel: példa #1, példa #2
(általam adott lineáris rekurziót kell tudni megoldani).
Fibonacci-számok zárt alakja. Lineáris rekurziók alaptétele (biz. nélkül), és alkalmazása
lineáris rekurziók megoldására. Fibonacci-számok kombinatorikus definíciója.
Elméleti segédlet a generátorfüggvény együtthatóinak kiszámolásához:
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása.
Kiegészítő olvasmány: Lineáris rekurziók középiskolás tárgyalása (avagy "honnan jön" a karakterisztikus polinom).
SZORGALMI: Catalan-számok (ld. Rekurziók prezentáció vége). SZORGALMI: Catalan-számok zárt alakjának elemi bizonyítása.
8. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója; hurokél, párhuzamos él. Csúcs fokszáma. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata). Részgráf; feszítő és feszített részgráfok.
Séta, vonal, út. Gráfok izomorfiája. Egyszerű gráf komplementere. Reguláris gráfok. Néhány speciális gráf: teljes gráf, út gráf, kör gráf.
Összefüggőség definíciója. A sétával való, illetve az úttal való összekötöttség kapcsolata.
9. Euler-vonal: Euler-vonal definíciója (nyílt és zárt). Euler-tétel.
A történelmi példa: Königsberg (ma Kalinyingrád) térképe Euler idejében, és a gráf.
10. Hamilton-út, Hamilton-kör: Kör. Hamilton-út, Hamilton-kör definíciója.
Dirac-tétel. Ore-tétel.
Egy (nem mindig alkalmazható) módszer annak igazolására, hogy a gráfban nincs Hamilton-kör/út (ha k pont elhagyásával..., ld. gyakorlat).
Érdekesség: Hamilton játéka.
11. Komponenesek, fák: Gráfok komponensei. Fák ekvivalens definíciói (hasznos minél többet ismerni, de elég annyi, amennyi előadáson előjött). Feszítőfák.
Levelek. Ághajtás operáció, fák struktúratétele (fák jellemzése ághajtás operációkkal). A fa éleinek száma. Gyökeres fák és lerajzolásaik.
12. Csúcsszínezések: Jó színezés és kromatikus szám definíciója. Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata.
Független ponthalmazok, α(G) paraméter. A χ(G) és α(G) paraméterek kapcsolata.
Nagy kromatikus számú háromszögmentes gráfok létezése (a bizonyítás SZORGALMI: lásd 3. konstrukció itt).
Mohó algoritmus (YouTube-videó a CooSpace-en), kromatikus szám felső becslése a maximális fokszám segítségével
(YouTube-videó a CooSpace-en).
13. Páros gráfok, síkgráfok: Páros gráfok definíciója. Páros gráfok jellemzése páratlan körökkel (a nehezebb irány gyakorlaton volt: IX/18.).
Fokszámösszeg a két színosztályban (a párosításos előadás végén jött elő + gyakorlaton). Teljes páros gráf.
Síkgráfok definíciója. Térképszínezési probléma, négyszín-tétel (bizonyítás nélkül).
A két alappélda nem síkgráfokra. Gráfok felosztása. Kuratowski-tétel (bizonyítás: csak az egyszerűbb irány).
SZORGALMI: Euler-formula.
14. Párosítások:
Párosítások, teljes párosítások, ν(G) paraméter.
Párosítások páros gráfokban: Kőnig-akadály (mit akadályoz meg, és miért; egy Kőnig-akadály hány párosítatlan pontot garantál A-ban).
Kőnig—Hall-tétel (a nehéz irány bizonyítása nélkül), Kőnig—Frobenius-tétel. Egy alkalmazás: teljes párosítás létezése reguláris páros gráfokban.
Párosítások általános gráfokban: Tutte-akadály (mit akadályoz meg, és miért), Tutte-tétel kimondása.
Kiegészítő segédanyag: Az órai anyagnál bővebb jegyzet párosításokról (a kihagyott bizonyításokkal együtt).
15. Extremális gráfelmélet: Turán-gráfok. Turán-tétel (biz. nélkül). Mantel-tétel.
SZORGALMI: A Turán-tétel bizonyítása.
16. Ramsey-elmélet: Ramsey-tétel (frissítés: bizonyítás ITT). Az R(k) Ramsey-szám definíciója. R(3) pontos értéke (a kapcsolódó feladat megoldásával együtt).
R(k) alsó és felső becslése (SZORGALMI: az alsó becslés bizonyításának vázlata).
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR (a legtöbb elhangzott definíció benne van)
Hajnal Péter távoktatásos prezentációi (ld. CooSpace / Linkek)
A fő segédanyag a korábbi előadó, Hajnal Péter internetes jegyzete a kurzushoz: 2019/2020-as tanév
A tanárszakos kurzushoz készült jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2014/2015-ös tanév
Kivetített prezentációk:
Kombinatorikai alapelvek (1. előadás),
Formális hatványsorok (2., 3. és 6. előadás),
Logikai szita (5. előadás),
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása (6. előadás),
Rekurziók, Fibonacci-számok, Catalan-számok (6. előadás),
Euler-tétel (8. előadás), Dirac-tétel (9. előadás),
Síkgráfok (11-12. előadás).
Euler-vonal: #1 (zárt),
#2 (zárt),
#3 (nyílt).
Hamilton-út: #1, #2.
Hamilton-kör: #1, #2, #3.
Komponensek: #1 (gráf 4 komponenssel),
#2 (gráf 3 komponenssel),
#3 (gráf 3 komponenssel).
Fa: #1, #2, #3.
Feszítőfa: #1.
Gyökeres fa lerajzolása: #1 (gyökér: 'r'), #2 (gyökér: 'a').
Síkgráf duálisa: #1, #2, #3, #4.
A duális gráf az eredeti gráf lerajzolásától is függ: #1.
Jó (csúcs)színezés: #1, #2.
Térképszínezési probléma / négyszíntétel szemléltetése: #1, #2.
Párosítás: #1 (nem teljes), #2 (teljes),
#3 (páros gráf egy párosítása), #4 (páros gráf egy A-t lefedő párosítása),
#5 (páros gráf egy teljes párosítása).
Kőnig-akadály: #1, #2. Lefogó ponthalmaz: #1.
Turán-gráf: #1 (T13,4, T14,4, T13,2 és T14,3), #2 (T7,3).
A képek többségét más oldalakról linkeltem (az URL-ből kiolvasható/megkereshető a forrás).
Hajnal Péter: Összeszámlálási problémák (Polygon Jegyzettár)
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, ingyenesen olvasható az interneten)
Bóna Miklós: Introduction to Enumerative Combinatorics (McGraw-Hill)
Reinhard Diestel: Graph Theory (Springer-Verlag, ingyenesen olvasható az interneten)
Richard P. Stanley: Enumerative Combinatorics, Vol. 1-2 (Cambridge University Press)
Benny Sudakov: Graph Theory (internetes jegyzet)
The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"
