Kombinatorika előadás (tanárszakosoknak), 2015/2016 tavasz

Hétfő 08:00-09:00, Grünwald Géza 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), ennek további részleteit a gyakorlatvezető hirdeti ki.

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 szerepelhetnek olyan elemek, amelyek ismerete pluszpontokat jelent a szóbeli vizsgán.

TEMATIKA

A zöld színnel jelölt ismeretéért pluszpont jár, ha az anyag többi része is jól ment.
A barna részek nem tartoznak a vizsgaanyaghoz, csak kiegészítő olvasmányok / érdekességek.

1. Alapok: Kombinatorikai alapelvek. Bijekció fogalma. Egy n elemű halmaz részhalmazainak száma. Karakterisztikus vektor.
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.
3. Sorbaállítások, átrendezések: Sorbaállítások. Egy n elemű halmaz sorbaállításainak száma. Átrendezések. Egy n elemű halmaz átrendezéseinek száma. Ciklusok. Az átrendezések ciklusokra bomlanak.
4. Multihalmazok: Multihalmaz definíciója, elemek multiplicitása, multiplicitásvektor. Részmultihalmazok száma. n elemű alaphalmaz feletti k elemű multihalmazok száma. Trinomiális tétel. Multinomiális tétel.
5. Logikai szita: A szita formula. A fixpont nélküli permutációk száma.
6. Rekurziók: Fibonacci-számok rekurzív definíciója. A Fibonacci-számok (egy lehetséges) kombinatorikus definíciója mint összeszámlálási problémára adott válasz. A Fibonacci-számok zárt alakja. Lineáris rekurziók megoldási módszere (lásd gyakorlat + segédanyag). Catalan-számok rekurzív definíciója és zárt alakja (bizonyítás nélkül).
7. 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áf. Séta, vonal, út.
8. Összefüggőség: Összefüggőség. "Sétával való összekötöttség" reláció, komponensek. Fák (elég annyi definíciót tudni, amennyi előjött előadáson). Levelek, ághajtás operáció. Fák jellemzése ághajtásokkal (fák "struktúratétele"). Fák élszáma. (Néhány fákkal kapcsolatos lemma bizonyítása gyakorlaton hangzott el.)
9. Euler-vonal: Euler-vonal definíciója (nyílt és zárt). Euler-tétel (a nyílt Euler-vonalra vonatkozó állítás bizonyítása csak pluszpontért). A történelmi példa: Königsberg (ma Kalinyingrád) térképe Euler idejében, és a gráf.
10. 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 (ld. gyakorlat). Dirac-tétel. (Ebből az Ore-tétel csak olvasmány.)
11. Csúcsszínezések: Páros gráfok definíciója és jellemzésük páratlan körökkel. Jó színezés és kromatikus szám. 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. Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata. Négyszín-tétel kimondása (lásd utolsó gyakorlat, vagy a síkgráfos prezentációban: 3/9. oldal 3. slide-jának alján).
12. Párosítások: Lefogó ponthalmazok, τ(G) paraméter. Párosítás, teljes párosítás, ν(G) paraméter. A τ(G) és ν(G) paraméterek kapcsolata. Párosítások páros gráfokban: Kőnig-akadály, Kőnig tétele, Kőnig—Hall-tétel, Kőnig—Frobenius-tétel (e három tételnél csak az egyszerű irány bizonyítása kell). Alkalmazás: Párosítások reguláris páros gráfokban.
13. Extremális gráfelmélet, Ramsey-elmélet: Mantel-tétel. Turán-gráfok (Tn,k). Turán-tétel (biz. nélkül). Monokromatikus ponthalmazok egy teljes gráf piros/kék-élszínezésében. Ramsey-tétel. Ramsey-számok. R(3) pontos értéke (ebből a középiskolás feladat megoldása: lásd gyakorlat, vagy 6. feladat itt a 3-4. oldalon). R(k) alsó és felső becslése (biz. nélkül).
14. Síkgráfok: Prezentáció. Nem vizsgaanyag, időhiány miatt kimaradt (de azért valamennyire a matematikai alapműveltséghez tartozik).

SEGÉDANYAGOK

A fő segédanyag a korábbi előadó, Hajnal Péter internetes jegyzete a kurzushoz: 2014/2015-ös tanév
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR
Lineáris rekurziók megoldása (+ ellenőrzés)
Fák ekvivalens definíciói
Kivetített prezentációk: Logikai szita, Euler-tétel, Dirac-tétel.

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 gyakorlatvezető honlapja
The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"

Főoldal