Kombinatorika előadás + gyakorlat (levelező), 2017/2018 ősz

KÖVETELMÉNYEK

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

TEMATIKA

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.

SEGÉDANYAGOK

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

GRÁFELMÉLETI FOGALMAK KÉPEKBEN

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).

AJÁNLOTT IRODALOM

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)

HASZNOS LINKEK

The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"

Főoldal