1. Bizonyítási módszerek: teljes indukció, skatulyaelv, indirekt bizonyítás, szükséges és elégséges feltételek (LPV 2.1, 2.4)

2. Kombinatorikus alapötletek: egymás utáni független döntések, Dobjuk ki a rosszat!, többszöri megszámlálás korrekciója. (LPV 1. fejezet)

3. Kombinatorikus alapfeladatok: sorbarendezési és kiválasztási problémák (sorrenddel vagy anélkül, ismétlődéssel vagy anélkül) (LPV 1. fejezet)

4. Kiválasztás ismétlődéssel: ismétléses kombináció és a pénzosztás kapcsolata és megoldásuk (LPV 3.4).

5. A binomiális tétel. A Pascal-háromszög, azonosságok a Pascal-háromszögben, kombinatorikus azonosságok algebrai és kombinatorikus bizonyítása (LPV 3.1, 3.5, 3.6).

6. A logikai szita-formula és alkalmazásai (LPV 2.3, és a honlapomon levő anyag)

7. Rekurziók, Fibonacci feladata, lépcsőmászás, a Fibonacci-számok. Azonosságok a Fibonacci-számokra (pl. összegük, teljes indukcióval). A Fibonacci-számok explicit képlete (LPV 4.1, 4.2, 4.3).

8. Barkochba, illetve Barkochba előre leírt kérdésekkel ( 2^n dologból n kérdés elég; kevesebb nem, ez csak vázlatosan volt)

9. Gráfok, irányított gráfok, a fokszámokra vonatkozó összefüggések. Fokszámok realizációja többszörös hurokélekkel, többszörös élekkel és egyszerű gráffal (LPV 7.1, valamint a honlapon levő anyag az egyszerű gráfokra vonatkozó bizonyítás nélkül)

10. Utak, körök, séták, vonalak, és kapcsolatuk. Összefüggőség. A komponenstétel, nem összefüggő gráfok elképzelése. (LPV 7.2)

11. Euler-vonal, Euler-körvonal, a königsbergi hidak problémája. Euler tétele az Euler-körvonal létezéséről. (LPV 7.3., a bizonyítás nem kell teljes részletességgel, de érteni kell)

12. Hamilton-út, Hamilton-kör, szükséges feltétel a létezésre. Dirac tétele. (anyag a honlapomon)

13. Fák: alternatív definíciók, fanövesztés, n csúcsú fának n-1 éle van. Összefüggő gráfoknak van feszítő fájuk. (LPV 8.1, 8.2, az ottaninál kevésbé részletesen volt előadáson)

14. Fák összeszámlálása, a Prüfer-kód. Cayley tétele a címkézett fák számáról (LPV 8.3, 8.4)

15. Síkbarajzolható gráfok, Fáry tétele (biz. nélk.). Euler-formula (és a szemléletes bizonyítás). K_5 és K_3,3 nem rajzolható síkba. n csúcsú síkgráfnak legfeljebb 3n-6 éle van. (LPV 12.1, 12.2).

16. Síkba rajzolt gráf duálisa. A hatszíntétel (biz.), az öt- és a négyszíntétel. Kuratowski tétele (biz. nélk.) (LPV részben 12.3, 13.4).

17. Gráfok színezése (csúcsok, élek, tartományok). Páros gráfok. Kromatikus szám, élkromatikus szám. Az alsó korlátok a legnagyobb teljes részgráf méretével, illetve a maximális fokszámmal. Brooks, Vizing tételei (mind biz. nélk.) Felső becslés a kromatikus számra a maximális fokszám segítségével. (LPV 13.2., 13.3.)

18. Minimális költségű feszítő fa keresése. Az optimista és a pesszimista stratégia. Bizonyítás abban az esetben, ha az élek költségei különbözőek.

-------------------------------------------------------------

Ajánlott irodalom: LPV: Lovász László, Pelikán József, Vesztergombi Katalin: Diszkrét matematika, Typotex Kiadó, 2006.

Egy mintakérdés:
I. 1. Definiálja a fa fogalmát! 2. Mit nevezünk körsétának egy gráfban? 3. Mondja ki Euler tételét Euler-körvonal létezéséről! 4. Fogalmazza meg a szitaformulát! 5. Milyen kapcsolat van páros gráfok és a kromatikus szám között? 6. Mondja ki a binomiális tételt! II. Síkbarajzolható gráfok (15. tétel).

Minden esetben pontos tételkimondásokat, illetve definíciókat várok, nem csupán mesét pl. a páros gráfok és a kromatikus szám kapcsolatáról. A II. kérdésnél a témakörbe tartozó definíciókat, tételeket kell elmondani, bizonyításokat a jó jegyért kérek. Ha valaki az egyszerű bizonyításokat sem tudja, akkor a II. kérdésnél nagyon fontos, hogy lényegében mindent összegyűjtsön az adott témáról.) A vizsga menetéről ld. a TÁJÉKOZTATÓ-t (külön file).