A félév során házi feladatokat tűzök ki CooSpace-en, melyek megoldását az ott megadott határidőig kell a rendszerbe feltölteni. A vizsgaidőszakban meghirdetett vizsgaidőpontokban pedig szóbeli vizsgák lesznek (beugróval); melyhez a pontos tematika 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.
Minden bizonyítást csak olyan részletességgel kell ismerni (teljesen / csak egyszerűbb részek / semennyire stb.), amennyire tárgyaltuk órán. A bordóval írt feladatok megoldásait gyakorlaton tárgyaltuk, ezeket a táblakép PDF-ekben találjuk.
1. Alapok (prezentáció): Kombinatorikus alapelvek. Bijekció. Egy n elemű halmaz részhalmazainak száma. Részhalmaz karakterisztikus vektora. Páros/páratlan elemszámú részhalmazok száma.
2. Binomiális együtthatók I. (prezentáció): A binomiális együtthatók definíciója. Képlet az (nk) binomiális együtthatóra.
A binomiális együtthatók rekurzív kiszámítási módja. Binomiális tétel.
3. Binomiális együtthatók II. (prezentáció): A Pascal-háromszög és alaptulajdonságai (szimmetria, egy sor elemeinek összege, stb.).
,,Hány olyan (ötös lottó) lottósorsolás-kimenetel van, amelyben van két szomszédos kihúzott szám?''
4. Multihalmazok (prezentáció): Multihalmazok definíciója.
Részmultihalmazok száma. Egy n elemű alaphalmaz feletti k elemű multihalmazok száma. Azon n elemű, természetes számokból álló sorozatok száma, amelyekre az elemek összege k.
5. Sorbaállítások (prezentáció): 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. ,,Van 12 különböző virágpalántánk, melyből 8 tulipán és 4 rózsa. Hányféle sorrendben tudjuk ezeket a palántákat kiültetni a virágoskertünk egy sorába úgy,
hogy ne kerüljön egymás mellé két rózsa?''
6. Logikai szita (prezentáció): A szita formula (a precíz bizonyítás elég 3 halmazig) + egy tetszőleges alkalmazás (3-nál több kiszitálandó halmazzal;
legalább olyan nehézségű, mint az órai/házi feladatok).
7. Gráfelméleti alapok (prezentáció): Egyszerű gráf, (általános) gráf definíciója. Fokszámok. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata).
Részgráf. Feszítő és feszített részgráfok. Teljes gráf.
Egyszerű gráf komplementere. Gráfok izomorfiája.
8. Összefüggőség, komponensek, páros gráfok (prezentáció + az előző témakör prezentációja):
Séta, vonal, út. Kör. Összefüggőség. Komponensek (csak vázlatosan!). Páros gráfok, ,,fokszámtétel'' páros gráfokra.
,,Bizonyítsuk be, hogy tetszőleges G egyszerű gráf esetén G vagy G összefüggő.''
9. Fák (prezentáció): Fák ekvivalens definíciói (hasznos minél többet ismerni, de elég annyi, amennyi előadáson volt).
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. Összefüggő gráfok (minimális) élszáma, körmentes gráfok (maximális) élszáma n ponton.
10. Euler-vonal, Hamilton-út, Hamilton-kör (prezentáció #1, prezentáció #2): Euler-vonal definíciója (nyílt és zárt). Euler-tétel (csak az a) pont egyszerűbb irányának bizonyításával).
Königsbergi hidak problémája: Königsberg (ma Kalinyingrád) térképe Euler idejében, és a gráf.
Hamilton-út, Hamilton-kör definíciója. Könnyű-e algoritmikusan eldönteni, hogy egy gráfban van-e Hamilton-út/kör?
11. Ramsey-elmélet (prezentáció): Egyszínű háromszögek a 6 pontú (és 5 pontú) teljes gráf piros/kék-élszínezéseiben; a probléma megfogalmazása
középiskolás feladatként is. Monokromatikus klikkek. Ramsey-tétel kimondása. ,,Igaz-e az, hogy 6 irracionális szám közül mindig kiválasztható három, hogy közülük bármely kettő összege irracionális?''
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
Euler-vonal: #1 (zárt),
#2 (zárt),
#3 (nyílt). 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)
A fő segédanyag Hajnal Péter internetes jegyzete a kurzushoz: 2022/2023-as tanév
GRÁFELMÉLETI FOGALMAK KÉPEKBEN
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.
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).
AJÁNLOTT IRODALOM
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, interneten is olvasható)
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"
