Kombinatorika (levelező), 2018/2019 tavasz

KÖVETELMÉNYEK

A félév során házi feladatok kerülnek feladásra, amelyek pontértéke és benyújtási határideje a honlapomon lesz közzétéve. A vizsgaidőszakban meghirdetett vizsgaidőpontokban pedig írásbeli vizsgák lesznek (beugróval); melyhez tematika és mintavizsga elérhető lesz a honlapomon A házi feladatokból és a vizsgából egyaránt legalább az ott elérhető pontszám 40%-át el kell érni (a házi feladatra vonatkozó kritérium a gyakorlati aláírás feltétele). A házi feladatok és vizsga százalékos eredménye 50-50%-os súllyal számít bele a végső érdemjegybe:
  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 óra alatt tett érdemi hozzászólással/hibajelzéssel, illetve szorgalmi feladatok megoldásával.

TEMATIKA

1. Részhalmazok: Bijekciók a kombinatorikában. Részhalmaz karakterisztikus vektora. Egy n elemű halmaz részhalmazainak száma. Páros/páratlan elemszámú részhalmazok száma.
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. 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. Az ((nk)) számok pontos értéke.
4. Sorbaállítások, átrendezések: Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma. Multihalmaz sorbaállítása, és a sorbaállítások száma. Trinomiális és multinomiális tétel (bizonyítás nélkül). Átrendezések (permutációk) definíciója. Egy n elemű halmaz átrendezéseinek száma. Ciklusok. Minden permutáció ciklusokra bomlik.
5. Logikai szita: A szita formula. Alkalmazás: Fixpont nélküli permutációk száma (elcserélt levelek problémája).
6. Rekurziók: Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni). Lineáris rekurziók és megoldásuk (általam adott lineáris rekurziót kell tudni megoldani). Fibonacci-számok rekurzív definíciója. Fibonacci-számok zárt alakja. Fibonacci-számok kombinatorikus definíciója (3-4. dia). Karakterisztikus polinom többszörös gyökei esetén a teendő: Lineáris rekurziók alaptétele (a másodrendű esetet elég tudni kezelni).
7. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója. Gráfok izomorfiája. Fokszámok. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata). Séta, vonal, út. Kör. Összefüggőség. Részgráf. Feszítő és feszített részgráfok. Egyszerű gráf komplementere. Teljes gráf.
8. 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.
9. Hamilton-út, Hamilton-kör: Hamilton-út, Hamilton-kör definíciója. Dirac-tétel (bizonyítás nélkül).
10. Ö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 előjött). Feszítőfák összefüggő gráfokban. Levelek. Ághajtás operáció, fák "struktúratétele" (fák jellemzése ághajtás operációkkal). A fa éleinek száma.
11. Páros gráfok: Páros gráfok definíciója és jellemzésük páratlan körökkel (csak az egyszerű irányt gondoltuk végig). A páros gráfok és a csúcsszínezések kapcsolata. Fokszámösszeg a két színosztályban.
12. Csúcsszínezések, síkgráfok: Jó színezés és kromatikus szám. Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata. Síkgráfok definíciója. Négyszín-tétel (biz. nélkül). A két alappélda nem síkgráfokra. A tananyagnál jóval bővebb segédanyag síkgráfokhoz. Ebből záróvizsgára kell (vizsgára nem): Gráfok felosztása, Kuratowski-tétel kimondása.
13. Párosítások: 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). Kőnig—Hall-tétel, Kőnig—Frobenius-tétel kimondása. Egy alkalmazás: teljes párosítás létezése reguláris páros gráfokban.

MINTAVIZSGA

FELADATSOROK

1. feladatsor 1. HF: 5. 20/b. (beadási határidő: február 16.), 2. HF: a nappalis feladatsorból a 3. és 4. feladat (beadási határidő: március 1.)
Sorbaállítások, átrendezések 3. HF: 2., 7. + az 1. feladatsorból a 29/b. (beadási határidő: március 23.)
Logikai szita 4. HF: 2., 6. (beadási határidő: március 24.)
Rekurziók 5. HF: 2., 6/b. (beadási határidő: április 13.)
Gráfelméleti alapok 5. HF: A 16. feladatból a G8 és G10 gráfok izomorfiájának igazolása (beadási határidő: április 13.)
Összefüggőség, séták, körök
Fák
Páros gráfok, kromatikus szám

SEGÉDANYAGOK

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: 2016/2017-es tanév
A tanárszakos kurzushoz készült jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2014/2015-ös tanév

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, #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, #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