Hétfő 14:00-16:00, Haar terem
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, akár későbbi előadásról / gyakorlatról is).
Részhalmaz karakterisztikus vektora. Hatványhalmaz. Egy n elemű halmaz részhalmazainak száma. Páros/páratlan elemszámú részhalmazok száma.
2. Binomiális együtthatók, multihalmazok (prezentáció): A binomiális együtthatók definíciója.
A Pascal-háromszög és alaptulajdonságai (rekurzió a binomiális együtthatókra; szimmetria; egy sor elemeinek összege).
Képlet az (nk) binomiális együtthatóra.
Multihalmazok szemléletes jelentése. Multihalmazok precíz definíciója + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai).
Részmultihalmazok száma. Az ((nk)) számok definíciója és pontos értéke.
((nk)) mint bizonyos vektorok száma.
SZORGALMI: Páros/páratlan elemösszegű k elemű részhalmazok (9. oldal, 4. feladat).
3. Polinomok, formális hatványsorok (prezentáció): Formális hatványsorok és polinomok definíciója.
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 (az alaptétel bizonyítása nélkül), egész kitevős hatványozás.
Az 1/(1-x) formális hatványsor.
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).
Az ((nk)) számok generátorfüggvénye.
Binomiális, trinomiális és multinomiális tétel (ld. 2. és 4. témakör prezentációiban).
SZORGALMI: Deriválás. Kompozíció. n-edik gyök, tört kitevőjű hatványok, Newton-formula (ld. Formális hatványsorok prezentáció vége).
4. Sorbaállítások, átrendezések (prezentáció): Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma.
Stirling-formula (biz. nélkül). Multihalmaz sorbaállításai, és ezek száma.
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.
Átrendezés (permutáció) definíciója. Egy n elemű halmaz átrendezéseinek száma. Bijekciók száma két n elemű halmaz között.
Ciklusok. 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.
5. Logikai szita (prezentáció): A szita formula (az általános eset bizonyítása csak jeles érdemjegyért).
Alkalmazás: Fixpont nélküli permutációk száma (ld. gyakorlat).
6. Rekurziók (prezentáció): 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. A Fibonacci-számok kombinatorikus definíciója. Lineáris rekurziók. Lineáris rekurziók megoldása generátorfüggvény-módszerrel (konkrét feladatot kell tudni megoldani): példa #1, példa #2,
példa #3 (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. Catalan-számok zárt alakja (biz. nélkül).
Kiegészítő segédanyag:
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása (és parciális törtekre bontás).
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 zárt alakjának elemi bizonyítása.
7. Gráfelméleti alapok (prezentáció): Egyszerű gráf, (általános) gráf definíciója; hurokél, párhuzamos élek.
Csúcs fokszáma. Reguláris gráfok. Izolált csúcs. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata). Irányított gráfok (informálisan), kifokok, befokok,
fokszámtétel irányított gráfokra. Néhány speciális gráf: teljes gráf, út-gráf, kör-gráf. Egyszerű gráf komplementere. Gráfok izomorfiája.
Csúcs- és élelhagyás. Részgráf; feszítő és feszített részgráf. Séta, vonal, út, kör. Összefüggőség definíciója. A sétával való, illetve az úttal való összekötöttség kapcsolata.
8. Euler-vonal (prezentáció), Hamilton-út, Hamilton-kör (prezentáció): 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.
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.
9. Komponenesek (prezentáció), 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.
10. Csúcsszínezések (prezentáció), síkgráfok (prezentáció): Jó színezés és kromatikus szám definíciója. Klikkek, független ponthalmazok, ω(G) és α(G) paraméterek. A χ(G) alsó becslése az ω(G)
ill. α(G) paraméterek segítségével.
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).
Páros gráfok definíciója. Páros gráfok jellemzése páratlan körökkel (csak kimondani). Fokszámösszeg egy páros gráf két színosztályában.
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 (bizonyítás nélkül). Gráfok felosztása. Kuratowski-tétel.
SZORGALMI:
Nagy kromatikus számú háromszögmentes gráfok létezése (bizonyítás: lásd 3. konstrukció itt).
Euler-formula.
11. Párosítások (prezentáció):
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 (csak pluszpontért, nem vizsgaanyag): 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).
12. Extremális gráfelmélet, Ramsey-elmélet (prezentáció): Mantel-tétel. Turán-gráfok. Turán-tétel (biz. nélkül).
SZORGALMI: A Turán-tétel bizonyítása.
Ramsey-tétel (+ bizonyítás 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)
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
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"
