- Előadás helye: Északi Tömb -1.62, ideje: csütörtök 10:15-12:00
- Könyv (részben fedi az eladást): Lovász - Pelikán - Vesztergombi: Diszkrét Matematika
-
Hetenkénti téma
Szeptember 12.
Leszámlálási alapfeladatok: Halmaz, részhalmaz, hatványhalmaz, döntési fa, kettes számrendszer, bijektív megfeleltetés. Sorozatok száma. Permutációk száma döntési fával. Közelítő megszámlálás, Stirling formula (csak kimondva). Rendezett és nem rendezett részhalmazok. Binomiális együtthatók.Szeptember 19.
Binomiális tétel, alapvető azonosságok binomiális együtthatókra. Anagrammák száma. Ajándékosztás és pénzosztás. A Pascal-háromszög. A legnagyobb binomális együttható nagyságrendje. Hány részre osztja a teret n általános helyzetű sík? 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 26.
A->B leképezések száma különböző mellékfeltételek mellett (a 16-féle feladat). Másodfajú Stirling számok, számpartíciók. Logikai szitaformula. Alkalmazás: Euler-féle fi-függvény. Skatulyaelv, alkalmazások: pontok az egységnégyzetben, n egész számból kiválasztható olyan nem-üres részhalmaz, melynek összege osztható n-nel. Az ikerparadoxon, logaritmus közelítése.Október 3.
Fibonacci számok. Fibonacci számokra vezeto feladatok: nyulak szaporodása, lépcson felmenés, szavak két szomszédos "b" nélkül, szmszédos számokat nem tartalmazó részhalmazok, adott elemszámú és tetszőleges elemszámú. Egyszerű azonosságok. Formula a Fibonacci számokra; 3 bizonyítás: indukció, mértani sorozatok, generátorfüggvény.Október 10.
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ő gráfok, komponensek. Pontok fokszáma és élek száma közti összefüggés, és alkalmazásai: Euler vonal, szimultán hegymászás.Október 17.
Fák és jellemzésük. Címkézett fák száma, Prüfer kód.Október 24.
Kruskal algoritmusa. Legrövidebb utak a súlyozatlan és súlyozott esetben, Dijkstra algoritmusa.November 7.
Irányított gráfok, erős és gyenge összefüggőség, erős és gyenge komponensek. Aciklikus gráfok. Euler vonal. Turnamentek. Hamilton út és kör turnamentben. Dirac tétele Hamilton körökről.November 14.
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; König min-max tétele; determináns azonosan 0 volta). Miért jó karakterizáció? (Artur-Merlin)November 21.
Alternáló utas algoritmus maximális párosításra páros gráfban. Síkráfok, Euler-fomula. Felső korlát síkráf élszámára. Síkgráfok jellemzése, Kuratowski tétele (csak kimondás).November 28.
Gráfok színezése. Háromszöget nem tartalmazó, nagy kromatikus számú gráf konstrukciója. Brooks tétele. Ötszíntétel.December 5.
Egységszakaszok gráfjának kromatikus száma. Erdős-de Bruijn Tétel, 2 bizonyítás (Kőnig Lemma ill. Zorn Lemma). Véges Ramsey szám R(k,m), binomiális becsléssel.December 12.
R(k,k) alsó becslése. Végtelen Ramsey tétel, abból a véges Ramsey tétel. Ramsey tétel t-halmazrendszerekre. Alkalmazás a konvex t-szögek problémájára (Happy End probléma).