A vizsga írásbeli lesz, az alábbi tematikából válogatott elméleti kérdésekkel, illetve a fogalmak és tételek megértését tesztelő egyszerűbb feladatokkal.
Beugró nem lesz, de alapvető hiányosságok esetén a vizsga automatikusan elégtelen. Az órákon pluszpontokat lehet szerezni érdemi hozzászólásokkal.
A gyakorlat aláírásának a legalább elégséges vizsgajegy a feltétele.
Osztályzat:
0 – 50: elégtelen
51 – 62: elégséges
63 – 75: közepes
76 – 87: jó
88 – 100: jeles
1. MINTAVIZSGA, 2. MINTAVIZSGA
1. Alapok, részhalmazok: A három kombinatorikus alapelv. Bijekció. Részhalmazok. Részhalmaz karakterisztikus vektora. Hatványhalmaz. Egy n elemű halmaz részhalmazainak száma. Kettős leszámlálás.
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. Egy n elemű alaphalmaz feletti k elemű multihalmazok száma.
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ásainak definíciója és száma. Trinomiális és multinomiális tétel.
Átrendezések (permutációk) definíciója. Egy n elemű halmaz átrendezéseinek száma. Bijekciók száma két n elemű halmaz között.
Ciklusok. Minden átrendezés ciklusokra bomlik.
5. Logikai szita: A szita formula. 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).
Fibonacci-számok rekurzív definíciója és zárt alakja. Fibonacci-számok egy kombinatorikus definíciója.
Catalan-számok rekurzív definíciója és zárt alakja.
Lineáris rekurziók. Másodrendű lineáris rekurziók megoldása (konkrét rekurziókat kell tudni megoldani).
Lineáris rekurziók alaptétele (bizonyítás nélkül).
SZORGALMI (nem vizsgaanyag): Catalan-számok zárt alakjának elemi bizonyítása.
7. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója. Fokszámok. A fokszámösszeg és az élszám kapcsolata. Gráfok izomorfiája. Részgráf. Feszítő és feszített részgráfok.
Séta, vonal, út. Kör.
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. Egy (nem mindig alkalmazható) módszer annak igazolására, hogy a gráfban nincs Hamilton-kör/út.
Dirac-tétel (bizonyítás nélkül).
10. Összefüggőség, fák: Összefüggőség. Elérhetőség reláció, komponensek.
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. 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. Csúcsszínezések, síkgráfok: Jó színezés és kromatikus szám definíciója.
Páros gráfok definíciója és jellemzésük páratlan körökkel (a nehezebb irány bizonyítása nélkül).
Klikkek, ω(G) paraméter. A χ(G) és ω(G) paraméterek kapcsolata.
Kromatikus szám felső becslése a maximális fokszám segítségével. (A bizonyításban használt mohó színezési algoritmus
illusztrációja, ahol
számok helyett igazi színekkel színezünk; a színpreferencia szerint 1 = világoszöld, 2 = világoskék, stb.).
Síkgráfok definíciója. Négyszín-tétel kimondása. A két alappélda nem síkgráfokra.
Nem vizsgaanyag: Olvasmány síkgráfokról.
12. Párosítások: Önállóan elsajátítandó anyagrész; segédanyag
ITT.
Párosítás, teljes párosítás, ν(G) paraméter definíciója.
Párosítások páros gráfokban: Kőnig-akadály definíciója, és annak végiggondolása, hogy egy Kőnig-akadály hány párosítatlan pontot garantál A-ban
(utóbbi a segédanyag 5. oldalának Észrevétel bekezdésében található);
Kőnig—Hall-tétel és Kőnig—Frobenius-tétel kimondása.
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR
A fő segédanyag Hajnal Péter internetes jegyzete a kurzushoz: 2016/2017-es tanév, 2013/2014-es tanév
Ez a jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2016/2017-es tanév
A 3. előadás kivetített prezentációi: Logikai szita. Rekurziók.
A 3. előadás kiosztott segédanyagai: (Másodrendű) lineáris rekurziók megoldása. Lineáris rekurziók alaptétele.
A 4. előadás kivetített prezentációja: Euler-tétel
Fák ekvivalens definíciói
Párosítások
Euler-vonal: #1 (zárt),
#2 (zárt), #3 (nyílt), #4 (nyílt).
Hamilton-út: #1, #2.
Hamilton-kör: #1, #2, #3, #4.
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 (gyökér: 'a'), #2.
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).
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"
⇦ | Főoldal |