Minden vizsgalapon négy kérdés fog szerepelni. Az itt szereplő több kérdés annak köszönhető, hogy többet szeretnék segíteni a felkészüléshez.
A kérdések kidolgozására 90 perc áll rendelkezésre. Mindenki törekedjen a tömör, lényegre törő érvelésre.
A 0-val kezdődő kérdések alapdefiníciók kimondásai. Megoldásukat az ELSŐ OLDALRA kell leírni. A dolgozat javításának első lépése annak ellenőrzése, hogy az ELSŐ OLDALON lévő tudásanyag hiányosságai nem zárják-e ki a sikeres vizsgát.
(0-1) Definiálja a párbaállító leképezés/bijekció fogalmát. Mit állíthatunk két halmazról, ha van köztük bijekció?
(0-1') Definiálja egy H halmaz feletti multihalmaz fogalmát. Mit értünk rész-multihalmazon? Mit értünk egy multihalmaz elemszámán.
(0-1'') Definiálja egy H halmaz sorbaállítását.
(0-1''') Definiálja egy H halmaz átrendezését/permutációját.
(0-2) Definiálja egy multihalmaz sorbarendezését.
(0-2') Definiálja egy sorbaállítás esetén az inverzióban álló elempárok fogalmát.
Definiálja a lineáris rekurziónak eleget tevő sorozat fogalmát.
(0-3) Definiáljuk a fa fogalmát.
(0-3') Definiálja a séta, elérhetőség reláció és összefüggő gráf fogalmát.
(0-3'') Definiálja a séta, elérhetőség reláció és egy gráf komponenseinek fogalmát.
(0-3''') Definiálja a feszítőfa fogalmát. Milyen gráfoknak van feszítőfája?
(0-3'''') Definiáljuk egy gráf Hamilton-körét.
(0-4) Definiáljuk egy gráf jó színezését és kromatikus számát.
(0-4') Definiáljuk a független halmaz, klikk és lefogó halmaz fogalmát.
(0-4'') Definiáljuk a Kőnig-akadály fogalmát.
1) Definiálja egy halmaz részhalmazának karakterisztikusvektorát.
Egy adott S halmaz részhalmazaihoz hozzárendeljük karakterisztikus vektorát. Az így kapott leképezésnek mi lesz az értelmezési tartománya, értékkészlete?
Igazolja, hogy a fenti leképezés bijekció.
1') Definiálja a multihalmaz, multihalmaz elemszáma és multihalmazok közötti tartalmazás fogalmát.
Mit értünk egy multihalmaz sorbaállítása alatt?
Hányféleképpen állíthatjuk sorba a MISSISSIPPI szó betűit? Mondjuk ki az általános tételt.
1'') Definiálja egy H halmaz sorbaállításának fogalmát.
Legyen H és H' két azonos elemszámú véges halmaz. Igazolja, hogy ugyanannyi sorbaállításuk van.
Legyen sn egy n elemű halmaz sorbaállításainak száma. Bizonyítsa be az sn-re vonatkozó rekurziót.
1''') Definiálja egy H halmaz sorbaállításának fogalmát.
Mikor mondjuk, hogy [n] egy sorbaállításában két elem inverzióban áll?
Definiálja az i(n,k) számokat és igazolja a rájuk vonatkozó rekurziót.
1'''') Definiálja egy H halmaz átrendezésének/permutációjának fogalmát.
Definiálja egy permutáció ciklusainak fogalmát.
Definiálja a c(n,k) számokat.
Igazoljuk a {c(n,k)}k=0oo sorozat generátorfüggvényére vonatkozó formulát.
2) Írjon fel egy összeszámlálási problémát, amely a Fibonacci-számokhoz vezet.
Vezessük le a Fibonacci-számokra vonatkozó rekurziót.
Írjuk fel a Fibonacci-számok generátorfüggvényét és vezessük le ebből a rájuk vonatkozó formulát.
2'') Definiáljuk mikor mondjuk, hogy egy sorozat kielégít/teljesít egy lineáris rekurziót.
Írjuk fel az alábbi lineáris rekurzióval definiált sorozat első néhány elemét: an=an-1+3an-2, ha n>=2 és a0=a1=1.
Az előadáson látott módszerrel határozzuk meg generátorfüggvényét.
Az előadáson látott módszerrel vezessünk le formulát az előző lineáris rekurzióval definiált sorozatra.
2''') Mondjuk ki a szita formulát.
Bizonyítsuk be a szita formulát.
Mutassuk be a szita formula egy alkalmazását.
2'''') Mondjuk ki a szita formulát.
Mutassuk be a szita formula egy alkalmazását.
A szita formulánál használt jelölésekkel élünk: A1, A2,..., An egy S halmaz részhalmazai. Az {1,2,...,n} halmaz egy I részhalmazára AI az I-beli indexekkel rendelkező A halmazok metszete. (A0=S). Legyen sk a k elemű indexszel rendelkező AI halmazok elemszámának összege. Értelmezzük a
Válaszunkat hozzuk lehető legegyszerűbb alakra.
3) Adjunk meg a fa fogalmának legalább két további (a (0-3)-mal természetesen ekvivalens) definícióját.
Hány éle van egy n pontú fának? Állításunkat bizonyítsuk be.
3') Mit értünk az alatt, hogy az elérhetőség reláció egy ekvivalenciareláció?
Bizonyítsa be a kimondott állítást.
A fenti ekvivalenciareláció osztályozza a gráf pontjait. Mondja ki ezen osztályozás általunk igazolt tulajdonságait.
3'') Definiáljuk egy út mohó (triviális) és csavarását, csavart növelését.
Mondjuk ki a Dirac-tételt.
Igazoljuk, hogy a Dirac-tétel feltételei mellett egy út, amely nem Hamilton-út csavart módon növelhető.
4) Mikor lehet egy gráfot 2 színnel jól színezni? Bizonyítsuk állításunkat.
Adjunk meg egy gráfot, amely pontjainak száma nem haladja meg 1.000.000-t, nem színezhető ki jól 10 színnel és nem tartalmaz háromszöget. A gráf konstrukciója mellett adjuk meg pontjainak számát is. A konstrukció helyességének bizonyítása nem szükséges.
Megjegyzés: Az előadáson egy általános konstrukció szerepelt, amelyből a kérdezett gráf kiolvasható. Az ott szereplő paramétert jó kell megválasztani és a pontszámot kiszámolni, ez a kis plusz sok diákot megzavar a fenti kérdés megválaszolásában.
4'') Definiáljuk hogy egy élszínezett teljes gráfban mikor mondjuk egy csúcshalmazra, hogy monokromatikus.
Mondja ki Ramsey- tételét.
Határozza meg az R(3) értéket. Válaszát indokolja.
Adjunk becslést R(4)-re.
4''') Definiálja a Turán-gráfokat.
Milyen méretűek a 111 pontú, 11 részes Turán-gráf osztályai? Hány éle van a 111 pontú, 11 részes Turán-gráfnak?
Mondja ki Turán tételét.
Igazolja Turán tételét háromszögmentes gráfokra (Mantel-tétel).