MTN243E
KOMBINATORIKA vizsgakérdések
2022 Tavasz
-
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?
- 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.
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?
-
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.
-
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.
-
Mit jelölünk [xd]P-vel?
Definiálja szavakkal, hogyan számolhatjuk ki egy
több tényezős polinomszorzatban xd 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.
-
Klikk és független csúcshalmaz fogalma.
Bevezető feladat a hat fős társaságról.
A feladat megoldása.
Ramsey tételének kimondása, igazolása.
-
Definiálja (nk) 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 (n0) és (nn)
értéke?
Írja le az (nk) 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.
-
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.
-
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.
-
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.
-
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.
-
Út, kör, Hamilton-út, Hamilton-kör fogalma.
Mohó út növelés és az elakadás analízise: csavart utak.
Út csavart növelése.
Dirac tétele.
-
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).
-
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.
-
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).
-
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: kimondás és bizonyítás.
-
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)n kifejtésére:
indoklás. Trinomiális tétel és bizonyítása.
-
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.
-
Definiálja mi a rekurzió. Adjon
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.
-
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.
(Itt a vizsgázó szabadon választhat,
melyik konstrukcióról beszél.)
-
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.
F0 tulajdonság és mértani sorozatok.
Formula Fibonacci-számokra.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.