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.
1. Részhalmazok, binomiális együtthatók: A kombinatorika alapelvei. Részhalmaz karakterisztikus vektora. Egy n elemű halmaz részhalmazainak száma.
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.
2. Multihalmazok: Multihalmazok szemléletes és precíz definíciója. Az alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai) precízen.
Részmultihalmazok száma. Egy n elemű halmaz feletti k elemű multihalmazok száma.
3. 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.
4. Logikai szita: A szita formula. Alkalmazás: Fixpont nélküli permutációk száma (elcserélt levelek problémája).
5. Lineáris rekurziók: Lineáris rekurziók és megoldásuk (általam adott lineáris rekurziót kell tudni megoldani).
Fibonacci-számok definíciója és zárt alakja.
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).
6. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója; hurokél, párhuzamos élek. Csúcs fokszáma. Reguláris gráfok.
Izolált csúcs. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata). Irányított gráfok (informálisan), kifokok, befokok, fokszámtétel irányított gráfokra.
Páros gráfok, "fokszámtétel" páros gráfokra. Teljes gráf. Egyszerű gráf komplementere. Gráfok izomorfiája. Csúcs- és élelhagyás. Részgráf; feszítő és feszített részgráf.
Séta, vonal, út, kör.
7. Euler-vonal, Hamilton-út, Hamilton-kör: Euler-vonal definíciója (nyílt és zárt). Euler-tétel (csak az egyszerűbb irány bizonyításával).
A történelmi példa:
Königsberg (ma Kalinyingrád) térképe Euler idejében, és a
gráf. Hamilton-út, Hamilton-kör definíciója. Dirac-tétel (bizonyítás nélkül). Egy elegendő feltétel ahhoz, hogy egy gráfban nincs
Hamilton-út/kör ("k pont elhagyása után...")
8. Ö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.
9. Csúcsszínezések, síkgrá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).
Jó színezés és kromatikus szám. Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata. Mohó algoritmus,
a chromatikus szám felső becslése a maximális fokszám segítségével. Síkgráfok definíciója. Négyszín-tétel (biz. nélkül).
A továbbiak vázlatosan: A két alappélda nem síkgráfokra. Gráfok felosztása, Kuratowski-tétel kimondása.
10. 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.
11. Ramsey-elmélet: Ramsey-tétel (bizonyítás nélkül). Az R(k) Ramsey-szám definíciója.
R(3) pontos értéke (a kapcsolódó középiskolás feladat megoldásával együtt). R(k) alsó és felső becslése (Erdős és Ramsey tételei).
A kombinatorika alapelvei
Részhalmazok, multihalmazok
Sorbaállítások, átrendezések
Logikai szita
Rekurziók, Fibonacci-számok, Catalan-számok
Gráfelméleti alapok
Euler-vonal, Euler-tétel
Hamilton-út, Hamilton-kör, Dirac-tétel
Kompenensek, fák.
Páros gráfok, csúcsszínezések
Síkgráfok
Párosítások
Ami félig volt (záróvizsgára mindkét témakör kell):
Extremális gráfelmélet és Ramsey-elmélet
Lásd CooSpace.
1. Kombinatorikus alapelvek, részhalmazok
2. Binomiális együtthatók, polinomok
3. Multihalmazok
4. Sorbaállítások, átrendezések
5. Logikai szita
6. Rekurziók
7. Gráfelméleti alapok
8. Séták, vonalak, utak, körök
9. Fák
10. Páros gráfok, kromatikus szám
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR (a legtöbb elhangzott definíció benne van)
A fő írott 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
Euler-vonal: #1 (zárt),
#2 (zárt),
#3 (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.
Gyökeres fa lerajzolása: #1 (gyökér: 'r'), #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.
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).
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"
