Hétfő 16:00-18:00, Szőkefalvi terem / online (Jitsi)
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 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 (prezentáció): A kombinatorika három alapelve (összeadási, szorzási, bijekciós). Bijekció. Egy (véges) halmaz elemszámának precíz definíciója.
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 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.
((nk)) mint bizonyos vektorok száma. Az ((nk)) számok pontos értéke. Az ((nk)) számok generátorfüggvénye.
Multihalmaz sorbaállításai, és a sorbaállítások száma.
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.
Bijekciók száma két n elemű halmaz között. Átrendezések (permutációk) definíciója.
Egy n elemű halmaz átrendezéseinek száma.
Minden permutáció ciklusokra bomlik. Az [nk] számok definíciója és generátorfüggvénye.
SZORGALMI: Páros és páratlan permutációk (vö. Diszkrét matematika kurzus).
SZORGALMI: Az [nk] számok generátorfüggvényének szép levezetése.
6. Logikai szita: A szita formula. Alkalmazás: Fixpont nélküli permutációk száma.
7. Rekurziók: Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni).
A Fibonacci-számok és Catalan-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. Catalan-számok zárt alakja (biz. nélkül).
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 alkalmazásai (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: Sétával való összekötöttség reláció, 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 (bizonyítás: 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. Teljes páros gráf. Páros gráfok jellemzése páratlan körökkel.
Fokszámösszeg a két színosztályban (gyakorlaton jött elő).
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.
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 (ld. utolsó gyakorlat).
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: Mantel-tétel. Turán-gráfok. Turán-tétel (biz. nélkül).
SZORGALMI: A Turán-tétel bizonyítása.
16. Ramsey-elmélet: Ramsey-tétel (+ bizonyítás csak jelesért). 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.
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"
