Az előadás anyaga a vizsgaidőszakban lesz számonkérve vizsga formájában. A vizsga egy rövid írásbeli beugróval kezdődik, mely átfogó módon teszteli a tananyag fogalmainak és tételeinek ismeretét, 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 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 vizsga eredményéhez (a vizsga súlya pontokra átszámítva körülbelül 50 pontnyi). 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: A három kombinatorikus alapelv. Bijekció. Skatulyaelv (példával). Kettős leszámlálás (egy tetszőleges példával későbbi anyagrészekből).
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 (a 3. előadáson szerepelt).
2. Binomiális együtthatók: A binomiális együtthatók definíciója. A binomiális együtthatók tulajdonságai (szimmetria, rekurzív kiszámítási mód stb.)
A Pascal-háromszög. Explicit képlet az (nk) binomiális együtthatóra. Polinomok, formális hatványsorok definíciója, összeadás, szorzás.
Több polinom / formális hatványsor szorzása. Binomiális tétel.
3. Multihalmazok: Multihalmazok szemléletes és matematikailag 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.
Az ((nk)) számok pontos értéke.
Rekurzió az ((nk)) számokra.
Az ((nk)) számok generátorfüggvénye.
Formális hatványsorok hányadosa. Műveleti tulajdonságok (nem kell betanulni; számolni kell tudni formális hatványsorokkal).
4. Sorbaállítások: 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 kiszámítási módja.
Az i(n,k) számok definíciója és egyszerű tulajdonságai. Az i(n,k) számok rekurzív kiszámítási módja és generátorfüggvénye (utóbbi biz. nélkül).
Multihalmaz sorbaállítása, és a sorbaállítások száma. Trinomiális és multinomiális tétel. SZORGALMI: Páros és páratlan permutációk (vö. algebra kurzusokon tanultakkal).
5. Átrendezések: 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. Permutációk diagramja. Ciklusok. Minden permutáció ciklusokra bomlik.
Az [nk] számok definíciója; egyszerű tulajdonságok és rekurzív kiszámítási mód. [n1] pontos értéke.
Az [nk] számok generátorfüggvénye + SZORGALMI: bizonyítás.
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 I: Fibonacci-számok és Catalan-számok: Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni). Fibonacci-számok rekurzív definíciója.
Fibonacci-számok kombinatorikus definíciója.
Catalan-számok rekurzív definíciója és kombinatorikus definíciói (a kombinatorikus definíciók közül
elég a Dyck-utas + biz.). Catalan-számok zárt alakja (a biz. opcionális: a generátorfüggvény zárt alakra hozása csak jeles érdemjegyhez,
az együtthatók kiszámolása csak pluszpontért: itt). Formális hatványsorok n-edik gyöke, tört kitevőjű hatványozás. Newton-formula.
8. Rekurziók II: Lineáris rekurziók: Lineáris rekurziók definíciója. Megoldás generátorfüggvény-módszerrel (általam adott lineáris rekurziót
kell tudni megoldani: 9 db kidolgozott példa).
Fibonacci-számok zárt alakja. Lineáris rekurziók alaptétele (biz. nélkül).
Nem vizsgaanyag, de hasznos lineáris rekurziók megoldá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).
9. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója. Hurokél, párhuzamos élek.
Néhány speciális gráf (Kn teljes gráf, Pn út-gráf, Cn kör-gráf).
Egyszerű gráf komplementere. Fokszám. A fokszámösszeg és az élszám kapcsolata. Izolált csúcs. Reguláris gráf. Csúcselhagyás, élelhagyás. Részgráf. Feszítő és feszített részgráfok. Séta, vonal, út. Kör. Összefüggőség.
A sétával / úttal összekötöttség ekvivalenciája.
10. 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.
11. Hamilton-út, Hamilton-kör: Hamilton-út, Hamilton-kör definíciója. Egy (nem mindig alkalmazható) módszer annak igazolására, hogy a gráfban nincs Hamilton-kör/út.
Dirac-tétel. Ore-tétel.
Érdekesség: Hamilton játéka.
12. Összefüggőség, fák: Összefüggőség. "Sétával való összekötöttség" reláció, komponensek.
Fák ekvivalens definíciói (hasznos minél többet ismerni, de elég annyi, amennyi előadáson volt).
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, és egyszerű következményei (összefüggő gráfok, körmentes gráfok élszámáról).
Gyökeres fák és lerajzolásaik.
13. Csúcsszínezések I. Páros gráfok definíciója és jellemzésük páratlan körökkel. Jó színezés és kromatikus szám. Független ponthalmazok, α(G) paraméter.
A kromatikus szám alsó becslése az α(G) paraméter (és a csúcsszám) segítségével.
Mohó színezési algoritmus (ebben az illusztrációban
számok helyett igazi színekkel színezünk; a színpreferencia szerint 1 = világoszöld, 2 = világoskék, stb.).
Kromatikus szám felső becslése a maximális fokszám segítségével.
14. Csúcsszínezések II., síkgráfok: Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata.
Nagy kromatikus számú háromszögmentes gráfok.
Síkgráfok definíciója. Térképszínezési probléma, négyszín-tétel (biz. nélkül). Hatszín-tétel (gyakorlaton bizonyítottuk).
A két alappélda nem síkgráfokra. Gráfok felosztása. Kuratowski-tétel (a nehéz irány bizonyítása nélkül).
SZORGALMI: Euler-formula. Kiegészítő olvasmány: Az Euler-formula következményei (a hatszín-tétel bizonyításának hiányzó része).
Ami kimaradt: Duális gráf, ötszín-tétel (5. és 6. fejezet).
15. Ramsey-elmélet: Ramsey-tétel. Az R(k) Ramsey-számok. R(3) pontos értéke. R(k) felső becslése (ami a Ramsey-tétel bizonyításából kijön).
R(k) alsó becslése (Erdős Pál tétele), és a bizonyítás alapgondolatának bemutatása R(20) alsó becslésével.
16. Extremális gráfelmélet: Mantel-tétel (megjegyzés: ez a Turán-tétel speciális esete). Turán-gráfok. Turán-tétel (biz. nélkül).
SZORGALMI: A Turán-tétel bizonyítása.
17. Párosítások: Lefogó ponthalmazok, τ(G) paraméter. Párosítások, teljes párosítások, ν(G) paraméter. A ν(G) és τ(G) paraméterek kapcsolata.
Kőnig-tétel (biz. nélkül). 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'' 5*-os jegyért/pluszpontért: itt), Kőnig—Frobenius-tétel. Egy alkalmazás: teljes párosítás létezése reguláris páros gráfokban.
Önállóan elsajátítandó: Tutte-akadály (mit akadályoz meg, és miért), Tutte-tétel kimondása.
Olvasmány/segédlet: Az órai anyagnál bővebb jegyzet párosításokról (a kihagyott bizonyításokkal együtt).
(folyamatosan bővül)
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR (sok elhangzott definíció benne van)
A fő segédanyag a korábbi előadó, Hajnal Péter internetes jegyzete a kurzushoz: 2014/2015-ös tanév, 2013/2014-es tanév
A tanárszakos kurzushoz készült jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2014/2015-ös tanév
A polinomok kétféle szemlélete közötti kapcsolat, néhány hasznos helyettesítés
Az ((nk)) számok generátorfüggvénye
Segédanyag a lineáris rekurziók megoldásához: A Fibonacci-számok zárt alakjának levezetése
Lineáris rekurziók alaptétele
Kiegészítés a lineáris rekurziók megoldásához: Középiskolás megközelítés + megoldás ellenőrzése (csak a másodrendű esetet tárgyalja részletesen).
Fák ekvivalens definíciói
Az Euler-formula következményei
Euler-vonal: #1 (zárt),
#2 (zárt), #3 (nyílt), #4 (nyílt).
Hamilton-út: #1, #2.
Hamilton-kör: #1, #2, #3, #4.
Komponensek: #1 (gráf 4 komponenssel),
#2 (gráf 3 komponenssel),
#3 (gráf 3 komponenssel).
Fa: #1, #2, #3.
Feszítőfa: #1, #2.
Gyökeres fa lerajzolása: #1 (gyökér: 'a'), #2 (gyökér: '1').
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, #3.
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).
Ramsey-elmélet: #1 (K6 egy piros-kék élszínezése, és a kialakuló monokromatikus háromszögek).
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"
| ⇦ | Főoldal |
