MTN243E    KOMBINATORIKA tematika

2022 Tavasz

1. Definiálja a bijekció, injekció, szürjekció fogalmát. Mit értünk egy bijekció inverzén? Mit értünk bijektív alapelv alatt? Adjon meg egy bijekciót egy n elemű halmaz részhalmazai és az n hosszú 0-1 vektorok között. Mindkét irányban írja le a párbaállítást. Mikor mondjuk, hogy egy halmaz véges? Indokolja meg miért jogos a kérdés: Hány részhalmaza van egy n elemű halmaznak?
2. Mit értünk összegzési elv alatt? Mit értünk szorzási alapelv alatt? Definiálja a szükséges fogalmakat is. Adjon két középiskolai feladatot, amely összegzési alapelvvel oldhatunk meg. Adjon két középiskolai feladatot, amely szorzási alapelvvel oldhatunk meg. Adjon egy olyan feladatot is, amely mindkét alapelvet használja. Egy n elemű halmaz részhalmazainak számát írja le rekurzióval. Indokolja válaszát.
3. Mit jelölünk [x^d]P-vel? Definiálja szavakkal, hogyan számolhatjuk ki egy több tényezős polinomszorzatban x^d együtthatóját. Írja fel képlettel is. Mondja ki a binomiális tételt. Bizonyítsa be a binomiális tételt. Definiálja a tételben szereplő fogalmakat.
4. Definiálja (ⁿ_k) számokat mint egy összeszámolási probléma eredményét. Milyen paraméterek mellett lesz ez a szám 0 és milyen esetben nem 0 értékű? Mi (ⁿ₀) és (ⁿ_n) értéke? Írja le az (ⁿ_k) számokat rekurzív módon. Indokolja válaszát. Mit értünk Pascal-háromszög alatt? Írja fel az első néhány sorát.
5. Definiálja mit értünk egy véges halmaz sorbaállításán. Definiálja a faktoriális függvényt (milyen számokra értelmeztük, hogyan számolható ki). Hány sorbaállítása van egy n elemű halmaznak? Hogy válatozik a sorbaállítások száma, ha az alaphalmazhoz egy új elemet adunk? Indokolja válaszait.
6. Definiálja mit értünk átrendezésen. Mi a köze egy véges halmaz átrendezéseinek a sorbaállításaihoz? Definiálja egy átrendezés ciklusát. Hogyan tekinthetünk minden átrendezésre? Indokolja válaszát. Hogy változik az átrendezések száma, ha az alaphalmazhoz egy új elemet adunk? Hány bijekció létezik két n elemű halmaz között? Indokolja válaszait.
7. Definiálja mit értünk multihalmazon. Definiálja az elem, elemszám, rész-multihalmaz fogalmát. Adjon motiváló példákat a multihalmaz fogalmára. Adott multihalmaz rész-multihalmazainak száma (tétel, bizonyítás). Adott halmaz feletti k elemű multihalmazok száma (tétel, bizonyítás).
8. Definiálja mit értünk multihalmazon. Definiálja az elem, elemszám, rész-multihalmaz fogalmát. Adjon motiváló példákat a multihalmaz fogalmára. Mit értünk egy multihalmaz sorbaállítása alatt. Adott multihalmaz sorbaállításainak száma (tétel, bizonyítás).
9. Definiálja mit értünk multihalmazon. Definiálja az elem, elemszám fogalmát. Adjon motiváló példákat a multihalmaz fogalmára. Adott multihalmaz sorbaállításainak száma (csak tétel kimondása). Binomiális tétel (x+y)ⁿ kifejtésére: indoklás. Trinomiális tétel és bizonyítása.
10. Definiálja mit értünk egy sorozat rekurzív definícióján. Adjon motiváló példákat: részhalmazok, sorbaállítások száma, Pascal-háromszög. Igazolja, hogy egy rekurzió egyértelműen definiál egy sorozatot.
11. Definiálja a Fibonacci-számokat összeszámlálási feladatként és rekurzióként. Igazolja a két definíció ekvivalenciáját. F₀ tulajdonság és mértani sorozatok. Formula Fibonacci-számokra.
12. Definiálja mit értünk lineáris rekurzióval definiált sorozaton. Hogyan lehet egy lineáris rekurzióval definiált sorozat általános elemére formulát adni. A leírásunkat egy példával illusztráljuk.
13. Mondjon egy középiskolás feladatot, ahol könnyebb a "rossz" elemeket összeszámolni mint a "jókat". Oldja is meg. Írja fel a szita formulát két és három részhalmazra. Indokolja is meg. Írja fel az általános szita formulát. Értelmezze a formula mindkét oldalát mint az elemek hozzájárulásainak összege. Igazolja a szita formulát.
14. Mondjon egy középiskolás feladatot, ahol könnyebb a "rossz" elemeket összeszámolni mint a "jókat". Oldja is meg. Írja fel a szita formulát két és három részhalmazra. Indokolja is meg. Írja fel az általános szita formulát. Írjon le egy alkalmazását a szitaformulának.
15. Definiálja az egyszerű gráf fogalmát. Vezesse be a gráfelmélet nyelvének alapfogalmait: illeszkedés, összekötöttség, végpont, szomszéd, stb. Mit értünk egy gráf lerajzolásán? Definiálja a gráf fogalmát.
16. Definiálja a gráf fogalmát. Vezesse be a gráfelmélet nyelvének alapfogalmait: illeszkedés, összekötöttség, végpont, szomszéd, stb. Mit értünk egy gráf lerajzolásán? Definiálja a fokszám fogalmát. Mondja ki a fokokra vonatkozó alaptételt. Igazolja is ezt. Mondjon ki következményeket.
17. Definiálja a séta fogalmát egy gráfban. Speciális séták: vonal, út, kör fogalma. Elérhetőség reláció fogalma és tualjdonságai. Ekvivalenciareláció és osztályozások. Úttal való elérhetőség.
18. Csúcsok, élek elhagyása egy gráfból. Részgráfok, feszített részgráfok, feszítő részgráfok. Komponensek és tulajdonságai. Összefüggő gráfok.
19. Fák, mint minimális összefüggő gráfok. Fák alternatív leírásai. Ághajtás operáció és kapcsolata a fákkal. Fák élszámára vonatkozó tétel.
20. Vonal, záródó vonalak, Euler-vonal fogalma. Akadályok Euler-vonal létezésére. Euler tétele (két alak). Mohó vonal növelés.
21. Út, kör, Hamilton-út, Hamilton-kör fogalma. Mohó út növelés és az elakadás analízise: csavart utak. Út csabart növelése. Dirac tétele.
22. Gráfok színezése, jó színezés, kromatikus szám. Példák. Kétszínezhető gráfok, páros gráfok, tétel.
23. Gráfok színezése, jó színezés, kromatikus szám. Példák. Mohó színezési algoritmus. Példák. Maximális fokszám és kapcsolat a színezési feladattal.
24. Gráfok színezése, jó színezés, kromatikus szám. Példák. Klikkek és kapcsolatuk a színezési problémával. Egy példa háromszögmentes nagy kromatikus számú gráfra.
25. Párosítások és a kapcsolódó optimalizálási probléma. Példák. Hogyan bizonyítható, hogy egy párosításnál nincs nagyobb a gráfunkban/páros gráfunkban?
26. Klikk fogalma. k-részes gráfok, Turán-gráfok és extremális tulajdonságuk. A Turán-tétel kimondása. Mantel-tétele.
27. Klikk és független csúcshalmaz fogalma. Bevezető feladat a hat fős társaságról. Ramsey tételének kimondása, igazolása.
28. A teljes gráf élszínezései, monokromatikus csúcshalmazok. Ramsey tételének kimondása. Ramsey-számok definíciója. Kis paraméterű Ramsey-számok becslései.