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) Definiáljuk a Fibonacci-számokat, mint egy nyulak szaporodására vonatkozó összeszámlálási problémát.
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 a Fibonacci-számokat, mint egy nyulak szaporodására vonatkozó összeszámlálási problémát.
Vezessük le a Fibonacci-számokra vonatkozó rekurziót.
Adjuk meg egy lineáris rekurziót, amelyet kielégít az an=4n-6n+2 sorozat.
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 ekvivalencia relá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') Mikor nevezünk egy gráfot regulárisnak?
Az előadáson milyen módon javasoltuk a mohó színezési algoritmus futtatását nem reguláris, összefüggő gráfokra?
Bizonyítsuk be, hogy a javasolt tulajdonságú sorrendje a csúcsoknak létezik (nem reguláris, összefüggő gráfok esetén)
4'') Definiáljuk a (0-4')-ben szereplő fogalmakhoz kapcsolódó optimalizálási kérdéseket.
Mondjuk ki és indokoljuk meg a fenti optimalizálási kérdések optimuma közötti kapcsolatokat.
4''') Adjunk becslést R(3,4)-re. Becslésünket indokoljuk. (Ramsey-tételére való hivatkozás nem megengedett!)
Mondjuk ki Ramsey-tételének kiterjesztését egy halmaz négy elemű részhalmazainak színezésére.
Megjegyzés: A Ramsey-tételére való hivatkozást azért tiltom, mert egy általános tétel speciális esetét kérdezem. Az általános tételbe speciális értékeket helyettesíteni nem nagy dolog. Amit itt kérek igazából egy bizonyítás. Teljes indukcióval fejtjük fel az eseteket. Ennek specializálása kell: R(3,3)-t becsüljük, majd R(3,4)-ra R(3,3) alapján adunk becslést. Ez egyszerűbb mint az előadáson elhangzott bizonyítás Ramsey-tételére, mégis sok diákot megzavar a kérdés fenti módon való megfogalmazása.
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.