Kombinatorika előadás (új BSc), 2017/2018 tavasz

Kedd 16:00-18:00, Vályi terem

KÖVETELMÉNYEK

Gyakorlat

A gyakorlaton maximum 60 pont szerezhető; ebből legalább 25 pontot kell elérni a gyakorlat aláírásához, ami az előadás teljesítésének előfeltétele is.

A gyakorlati pontszám két zárthelyi dolgozat pontszámából (20+20 pont) és a házi feladatok eredményéből (10×2 pont) tevődik össze. A zárthelyi dolgozatok időpontjait a gyakorlatvezető jelöli ki, a vizsgaidőszak első hetében az egyik zh javítható/pótolható. A két zh-írós órát leszámítva minden gyakorlaton házi feladatok lesznek feladva, 2-2 pont értékben, és a következő órán kell írásban benyújtani a megoldásokat. Az így szerzett 12 házifeladat-pontból a 10 legjobb kerül beszámításra félév végén. (A házi feladatok nem javíthatók/pótolhatók.)

Ezenfelül a gyakorlaton legfeljebb 10 pluszpont gyűjthető órai munkával, illetve a szorgalmi feladatok otthoni megoldásával.

Előadás

Az előadásvizsgán maximum 40 pont szerezhető (tehát a vizsga 40%-os súllyal számít bele a végső érdemjegybe).

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á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, pl. gyakorlatról). 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. Páros/páratlan elemszámú részhalmazok száma (II. pont itt, vagy 1. gyakorlat). 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). SZORGALMI: n-edik gyök, tört kitevőjű hatványok, Newton-formula (ld. Formális hatványsorok II. 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. 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 gyors 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. Multihalmaz sorbaállítása, és a sorbaállítások száma. Trinomiális és multinomiális tétel (bizonyítás: ld. gyakorlat). 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 (elcserélt levelek problémája); szürjektív leképezések száma (ld. gyakorlat).
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. Lineáris rekurziók, és megoldásuk generátorfüggvény-módszerrel (á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. 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 (ld. Rekurziók prezentáció vége). 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; 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. Összefüggőség. 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. Hasznos ismerni: Irányított gráfok (2. oldal vége).
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: 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. Érdekesség: Hamilton játéka.
12. Összefüggőség, fák: Összefüggőség. 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). Erdők. 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 definíciója. Klikkek, ω(G) paraméter. 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. A χ(G) és ω(G) paraméterek kapcsolata. Nagy kromatikus számú háromszögmentes gráfok (lásd 3. konstrukció itt).
14. Csúcsszínezések II., síkgráfok: Kromatikus szám felső becslése a maximális fokszá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.). Síkgráfok definíciója. Térképszínezési probléma, négyszín-tétel (biz. 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: Euler-formula.
15. 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. Párosítások páros gráfokban: 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 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. Kőnig-formula (biz. nélkül). SZORGALMI: Párosítások általános gráfokban: 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).
16. Extremális gráfelmélet: Turán-gráfok. Turán-tétel (biz. nélkül). Mantel-tétel. SZORGALMI: A Turán-tétel bizonyítása.
17. Ramsey-elmélet: Ramsey-tétel. Az R(k) Ramsey-számok. R(3) pontos értéke (a kapcsolódó feladat megoldásával együtt). 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, SZORGALMI: a bizonyítás vázlata).

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: 2016/2017-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: Formális hatványsorok II. (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-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.
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.
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

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

Főoldal