- Előadás helye: Déli Tömb 00.718, ideje: péntek 8:15-10:00
- Könyv (részben fedi az előadást): Lovász - Pelikán - Vesztergombi: Diszkrét Matematika
-
Hetenkénti téma
Szeptember 14.
Leszámlálási alapfeladatok: Halmaz, részhalmaz, hatványhalmaz, döntési fa, kettes számrendszer, bijektív megfeleltetés. Közelítő megszámlálás. Sorozatok száma. Permutációk száma döntési fával. Stirling formula (csak kimondva). Anagrammák. Rendezett és nem rendezett részhalmazok. Variációk, kombinációk ismétlés nélkül és ismétléssel. Binomiális együtthatók, binomiális tétel, alapvető azonosságok binomiális együtthatókra. Gyöngyszem: Ha véges sok síkbeli pont nincs egy egyenesen, akkor van 2 pontú egyenes (Sylvester-Gallai Tétel). Következmény: n síkbeli pont, ha nincs mind egy egyenesen, legalább n egyenest határoz meg.Szeptember 21.
További azaonosságok binomiális együtthatókra. Ajándékosztási, pénzosztási lehetőségek száma, polinomiális együtthatók. A Pascal-háromszög. A legnagyobb binomális együttható nagyságrendje. Logikai szitaformula. Gyöngyszem: Cauchy tétele poliéderek merevségéről.Szeptember 28.
Az A->B leképezések leszámlálásának 16 verziója. Partíciók, másodfajú Stirling-számok, rekurziójuk. Skatulyaelv, alkalmazások: pontok az egységnégyzetben, n egész számból kiválasztható olyan nem-üres részhalmaz, melynek összege osztható k-val. Az ikerparadoxon, logaritmus közelítése. Fibonacci számok, egyszerű azonosságok.Október 5.
Formula a Fibonacci számokra. Fibonacci számokra vezető feladatok: lépcsőn felmenés, szavak két szomszédos "b" nélkül. Példa más hasonló rekurzióra vezető feladatra. Gráfok fogalma, hurokél, többszörös él, egyszerű gráfok. Séták, vonalak, utak, körök és kapcsolatuk. Összefüggő és nem összefüggő gráfok, komponensek. Pontok fokszáma és élek száma közti összefüggés, és alkalmazásai: Sperner Lemma, szimultán hegymászás.
Október 12.
Fák és jellemzésük. Címkézett fák száma, Prüfer kód.Október 19.
Feszítő fák. Szélességi és mélységi keresés. Kruskal algoritmus és változatai. Dijkstra algoritmusa.Október 26.
Euler-vonal létezésének szükséges és elegendő feltétele. Hamilton-kör létezésének szükséges feltételei. Dirac tétele. Irányított gráfok, kifok, befok. Gyenge és erős összefüggőség és összefüggő komponensek. Irányított kört nem tartalmazó gráfok. Euler vonal irányított gráfokban. Turnamentek. Hamilton-út és Hamilton-kör turnamentekben.November 9.
Síkráfok, Euler-fomula. Felső korlát síkráf élszámára. Síkgráfok jellemzése, Kuratowski tétele.November 16.
Gráfok színezése. Háromszöget nem tartalmazó, nagy kromatikus számú gráf konstrukciója. Brooks tétele. Ötszíntétel.November 23.
Egységszakaszok gráfjának kromatikus száma. Erdős-de Bruijn Tétel, 2 bizonyítás (Kőnig Lemma ill. Zorn Lemma). Párosítások páros gráfokban, szükséges és elégséges feltétel bizonyítása.November 30.
Párosítások páros gráfokban: Következmények és alkalmazások (reguláris páros gráfban van teljes párosítás; duplán sztochasztikus mátrixok; Kőnig min-max tétele; determináns azonosan 0 volta). Alternáló utas algoritmus maximális párosításra páros gráfban. Miért jó karakterizáció? (Artur-Merlin)December 7.
Extremális gráfelmélet elemei: Mantel, Turán, Erdős-Reiman, Kővári-Sós-Turán tételei. Geometriai alkalmazások: egységszakaszok száma, nagy távolságok száma n síkbeli pont között. Véges geometriák alkalmazása négyszögmentes gráfok konstrukciójára.December 14.
Véges Ramsey szám R(k,p), binomiális becsléssel; R(k,k) alsó becslése; végtelen Ramsey tétel, abból a véges Ramsey tétel; végtelen t-halmazrendszer Ramsey; alkalmazás a konvex t-szögek problémájára (alsó és pontosabb felső becslés csak megjegyzés formájában).