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 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 a Fibonacci-számok 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á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 klikk fogalmát egy gráfban.
(0-4'') Definiáljuk a párosítás fogalmát egy gráfban.
(0-4''') Mikor modnjuk egy gráfra, hogy síkgráf?
1) 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 az (nk) számokat.
Mondja ki és igazolja a rájuk vonatkozó rekurziót.
Írja fel az (nk) számokat, ha 0 <= k <=n <=8.
Találjon ki egy feladatot, amelyre n2(2nn) a válasz.
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.
Keressünk a rekurzív összefüggésnek elegettevő mértani doorzatokat.
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.
Keressünk mértani sorozatokat, amelyek kielégítik a rekurzív összefüggést.
A gyakorlaton 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.
3) Adjunk meg a fa fogalmának legalább két további (a (0-3)-mal természetesen ekvivalens) definícióját.
Definiálja a gráfokra vonatkozó ághajtás oprációt.
Mondja ki az ághajtás és a fák fogalma közötti kapcsolatot. A kapcsolat egyik irányát igazolja.
Hány éle van egy n pontú fának?
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. Mitmondhatunk egy ekvivalenciaosztályba eső csúcsok és a köztük vezető élek által alkotott gráfról? Igazolja állítását.
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) Írja le a mohó színezési eljárást.
Mit mondtunk ennek színigényéről? Igazolja ezt az állítást.
Edott a síkon egyenesek egy rendszere, amelyek közül semelyik három nem megy át közös ponton. Igazolja, hogy metszéspontjaik három színnel kiszínezhetők úgy, hogy semelyik szomszédos metszéspont-pár sem kapja ugyanazt a színt (két metszéspont szomszédos, ha egyeneseink közül átmegy mindkettőn valamelyik és köztük nincs más metszéspont).
4') Definiálja a Kőnig-akadály fogalmát.
Mit akadályoz meg egy ilyen akadály léte?
Definiálja a párosít'asokkal és lefogásokkal kapcsolatos optimalizálási problémát. Mi a kettő között a kapcsolat? Miért?
4'') Definiálja az n csúcsú, k részes Turán-gráf fogalmát.
Adjon példát olyan n pontú egyszerű gráfra, amelynek sok éle van és nem tartalmaz háromszöget.
Mondja ki Mantel tételét és igazolja is.