Minden vizsgalapon öt 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áljuk a fa fogalmát.

(0-2) Definiáljuk egy gráf Hamilton-körét.

(0-3) Definiáljuk egy gráf jó színezését.

(0-4) Definiáljuk a független halmaz, klikk és lefogó halmaz fogalmát.

(0-5) Definiáljuk a Tutte-akadály fogalmát.

(0-5') Definiáljuk a monokromatikus halmaz fogalmát és az R(k,l) Ramsey-számokat.

1) Adjunk meg a fa fogalmának legalább három további (a (0-1)-gyel természetesen ekvivalens) definícióját.

Hány éle van egy n pontú fának? Állításunkat bizonyítsuk be.

2) 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 van gráfunkban Hamilton-út.

3) 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 feladat szerepelt, amelyből a kérdezett gráf kiolvasható. Ennek tárgyalásakor a pontszámra nem volt szükségünk, ez sok diákot megzavar a fenti kérdés megválaszolásában.

4) Definiáljuk a (0-4) 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.

Írjuk le a független ponthalmaz keresésére szolgáló mohó algoritmust.

5) Mit akadályoz meg egy Tutte-akadály léte? Indokoljuk válaszunkat.

Egy konkrét Tutte-akadály előfordulásánál mit mondhatunk a legnagyobb párosítás méretéről?

5)' 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.