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 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-1') Definiálja a séta, elérhetőség reláció és összefüggő gráf fogalmát.

(0-1'') Definiálja a séta, elérhetőség reláció és egy gráf komponenseinek fogalmát.

(0-2) 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-3') Definiáljuk egy gráf jó színezését és kromatikus számát.

(0-4) Definiáljuk a párosítás fogalmát és az erre vonatkozó javító út fogalmát.

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

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

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.

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

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 egy út, amely nem Hamilton-út csavart módon növelhető.

2)' 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 kiszamolni, ez a kis plusz sok diákot megzavar a fenti kérdés megválaszolásában.

2)'' 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)

3) Legyen M egy párosítás a G gráfban. Írjuk le azt a címkézési eljárást, amely során javító út kezdeményeket növelünk és amely egy nem bővíthető F kereső erdőhöz vezet.

Hogyan alkalmaztuk ezt az eljárást páros gráfokra?

Sikertelen keresés esetén miért lehetünk biztosak, hogy nincs javító út?

3)' 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?

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.

Írjuk le a független ponthalmaz keresésére szolgáló maív mohó algoritmust és azt a módosítását, amit az előadás során vizsgáltunk.

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.