Kombinatorika előadás (új BSc), 2015/2016 tavasz

Kedd 12:00-14:00, Haar Alfréd terem

KÖVETELMÉNYEK

Az előadás teljesítésének előfeltétele a gyakorlaton megszerzett aláírás. A vizsgára legfeljebb 60 pontot lehet hozni a gyakorlatról, mely a két zárthelyi dolgozat és a házi feladatok pontszámaiból tevődik össze (20+20+20 pont), további részletek a gyakorlat honlapján.

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, 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 vizsgán legfeljebb 40 pont szerezhető, ebbő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 megszerzett pontszám hozzáadódik a gyakorlatról hozott pontszámhoz, é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.

TEMATIKA

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ó. Hatványhalmaz. Részhalmaz karakterisztikus függvénye és karakterisztikus vektora. Egy n elemű halmaz részhalmazainak száma. Skatulyaelv (példával). Kettős leszámlálás (példával).
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 (lásd gyakorlat). Páros/páratlan elemszámú részhalmazok száma (II. pont itt, vagy gyakorlat). SZORGALMI: Páros/páratlan elemösszegű k elemű részhalmazok (9. oldal, 4. feladat).
3. Polinomok, formális hatványsorok: Polinomok definíciója, műveletek polinomokkal, több polinom szorzása (2. tulajdonság itt). Formális hatványsorok definíciója, alapműveletek (összeadás és szorzás), hatványozás, osztás. Formális hatványsor foka. Generátorfüggvények. Deriválás, kompozíció. Formális hatványsorok műveleti tulajdonságai (nem kell betanulni; számolni kell tudni formális hatványsorokkal), többtényezés szorzat. 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, a lényeg, hogy konkrét polinom/polinom hatványsor együtthatóit tudjuk kiszámolni). n-edik gyök, tört kitevőjű hatványok, Newton-formula (lásd 7. előadás prezentációjának 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 (lásd gyakorlat). Az ((nk)) számok pontos értéke. Az ((nk)) számok generátorfüggvénye.
5. 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.
6. Á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. Ciklusok. Minden permutáció ciklusokra bomlik. Az [nk] számok definíciója, rekurzív kiszámítási módja és generátorfüggvénye (utóbbi biz. nélkül). SZORGALMI: Az [nk] számok generátorfüggvényének szép levezetése.
7. Logikai szita: A szita formula. Alkalmazások: Fixpont nélküli permutációk száma; szürjektív leképezések száma.
8. Rekurziók: 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 zárt alakja. Lineáris rekurziók, és megoldásuk generátorfüggvény-módszerrel (általam adott lineáris rekurziót kell tudni megoldani). Lineáris rekurziók alaptétele (biz. nélkül). 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). 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. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója. Fokszámok. A fokszámösszeg és az élszám kapcsolata. Részgráf. Feszítő és feszített részgráfok. Séta, vonal, út. Összefüggőség. Kör. Gyakorlaton előkerült fogalmak: Teljes gráf. Egyszerű gráf komplementere. Gráfok izomorfiája. Reguláris gráfok. Teljes páros gráf. Hasznos ismerni: Irányított gráfok.
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 (utóbbit gyakorlaton bizonyítottuk). 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 (lásd gyakorlat, további konstrukciók itt). 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).

SEGÉDANYAGOK

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
Kivetített prezentációk: 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 (7. 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).

GRÁFELMÉLETI FOGALMAK KÉPEKBEN

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).

AJÁNLOTT IRODALOM

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)

HASZNOS LINKEK

A gyakorlat honlapja
The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"

Főoldal