Minden vizsgalapon négy definíció (D), két közepes (K) és egy nagyobb kérdés (N) 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.

(D-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ó?

(D-1') Definiálja egy H halmaz feletti multihalmaz fogalmát. Mit értünk egy multihalmaz elemszámán.

(D-1'') Definiálja egy H halmaz sorbaállítását.

(D-1''') Definiálja egy H halmaz átrendezését/permutációját.

(D-2) Definiálja egy multihalmaz sorbarendezését.

(D-2') Definiálja a Fibonacci-számok fogalmát.

(D-3) Definiáljuk a fa fogalmát.

(D-3') Definiálja a séta, elérhetőség reláció és összefüggő gráf fogalmát.

(D-3'') Definiáljuk egy gráf Hamilton-körét.

(D-4) Definiáljuk egy gráf jó színezését és kromatikus számát.

(D-4') Definiáljuk a klikk fogalmát egy gráfban.

(D-4'') Definiáljuk a párosítás fogalmát egy gráfban.

(K-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.

(K-1') Definiálja az (ⁿ_k) számokat.

Mondja ki és igazolja a rájuk vonatkozó rekurziót.

Írja fel az (ⁿ_k) számokat, ha 0 <₌ k <₌n <₌8.

Találjon ki egy feladatot, amelyre n²(²ⁿ_n) a válasz.

(K-1'') 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: a_n=a_n-1+3a_n-2, ha n>₌2 és a₀=a₁=1.

(K-2) Adjunk meg a fa fogalmának legalább két definícióját.

Definiálja a gráfokra vonatkozó ághajtás operációt.

(K-2') 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.

(K-2) Írja le a mohó színezési eljárást.

Mit mondtunk ennek színigényéről? Igazolja ezt az állítást.

(K-2') Definiálja a párosítás fogalmát.

Definiálja a lefogó ponthalmaz fogalmát.

Definiálja a párosításokkal és lefogásokkal kapcsolatos optimalizálási problémát. Mi a kettő között a kapcsolat? Miért?

(N) Mondjuk ki a szita formulát.

Bizonyítsuk be a szita formulát.

Mutassuk be a szita formula egy alkalmazását.

(N') Mondja ki az ághajtás és a fák fogalma közötti kapcsolatot. A kapcsolatot igazolja.

Hány éle van egy n pontú fának? Miért?

(N'') Adjon példát olyan n pontú egyszerű gráfra, amelynek ``sok'' éle van és nem tartalmaz háromszöget.

Mondja ki Turán tételét tételét és igazolja is.

(N''') 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ő.