Csütörtök 8:00-10:00, Grünwald Géza terem
Gyakorlatról legfeljebb 60 pontot lehet hozni, 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 – 49: elégtelen
50 – 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 lila 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 zöld 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.
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 (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. Binomiális együtthatók összehasonlítása. Binomiális tétel.
SZORGALMI: Binomiális együtthatók paritása. (Bizonyítás ITT [9.tétel],
a Pascal-háromszög Sierpiński-háromszögszerű ,,paritástérképének'' magyarazáta pedig ITT.)
Páros/páratlan elemösszegű k elemű részhalmazok (9. oldal, 4. feladat).
3. Multihalmazok (prezentáció):
Multihalmazok szemléletes jelentése. Multihalmazok precíz definíciója + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai).
Részmultihalmazok száma. Egy n elemű alaphalmaz feletti k elemű multihalmazok száma.
((nk)) mint bizonyos vektorok száma.
Az ((nk)) számok generátorfüggvénye.
4. Sorbaállítások (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. Trinomiális és multinomiális tétel.
Inverzióban álló elempár. Inverziószám definíciója és gyors kiszámítási módja. Páros/páratlan permutációk definíciója inverziószámmal (a Diszkrét matematika kurzuson tanult definícióval
való ekvivalencia bizonyítása itt: ITT).
Az inverziótábla egy bijekció Sn és {0,...,n-1}×...×{0,1}×{0} között.
SZORGALMI: Az i(n,k) számok definíciója és generátorfüggvénye.
5. Átrendezések (prezentáció):
Á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. Egy n elemű halmaz 1 ciklusból álló permutációinak száma.
Az [nk] számok definíciója és generátorfüggvénye.
Az [nk] számok generátorfüggvényének szép levezetése.
6. Logikai szita (prezentáció): A szita formula.
Alkalmazás: Fixpont nélküli permutációk száma (elcserélt levelek problémája).
7 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.
Átfedés más témakörökkel: Az 1/(1-x)n formális hatványsor.
Binomiális, trinomiális és multinomiális tétel (ld. a 2. és 4. témakörök 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).
8. Rekurziók I. (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 és Catalan-számok (egy) kombinatorikus jelentése. Catalan-számok zárt alakja (biz. nélkül).
Lineáris rekurziók. Lineáris rekurziók alaptétele (biz. nélkül), és alkalmazása lineáris rekurziók megoldására.
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.
9. Rekurziók II. (prezentáció): Lineáris rekurziók megoldása generátorfüggvény-módszerrel (konkrét feladatot kell tudni megoldani): példa #1, példa #2.
Fibonacci-számok zárt alakja.
Kiegészítő segédanyag:
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása (és parciális törtekre bontás).
10. 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. Páros gráfok, "fokszámtétel" páros 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.
11. Euler-vonal (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.
12. Hamilton-út, Hamilton-kör (prezentáció): Hamilton-út, Hamilton-kör definíciója. Dirac-tétel. Ore-tétel.
Egy (nem mindig alkalmazható) módszer a Hamilton-kör/út-mentesség igazolására (ld. következő prezentáció).
Érdekesség: Hamilton játéka.
13. Komponenesek, fák (prezentáció): Az elérhetősé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. Összefüggő és körmentes gráfok élszámbecslései. Erdők.
Gyökeres fák és lerajzolásaik (a lerajzolhatóságot csak kimondani).
14. Csúcsszínezések (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.
SZORGALMI: Nagy kromatikus számú háromszögmentes gráfok létezése (bizonyítás: lásd 3. konstrukció itt).
15. Síkgráfok (prezentáció): 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. Síkra rajzolt gráf tartományai, Euler-formula (bizonyítás csak jelesért).
16. 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: Tutte-tétel kimondása (+ miért szükségesek a feltételek).
Lefogó ponthalmazok, τ(G) paraméter. A ν(G) és τ(G) paraméterek kapcsolata, Kőnig tétele.
Kiegészítő segédanyag: Az órai anyagnál bővebb jegyzet párosításokról (a kihagyott bizonyításokkal együtt).
17. Extremális gráfelmélet (prezentáció): Turán-gráfok. Turán-tétel (biz. nélkül). Mantel-tétel.
SZORGALMI: A Turán-tétel bizonyítása.
18. Ramsey-elmélet (prezentáció):
Ramsey-tétel (+ bizonyítás). Az R(k) Ramsey-szám definíciója. R(3) pontos értéke (a kapcsolódó középiskolás feladat megoldásával együtt).
R(k) alsó és felső becslése (Erdős és Ramsey tételei).
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"
