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 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-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-5) 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) Írjuk le, egy tartalmazásra nézve zárt H halmazrendszer (ha H egy A eleme és B részhalmaza A-nak, akkor B is H-nak eleme) és az alaphalmazon adott súlyfüggvény (amely a halmazokhoz is súlyt rendel) esetén hogyan kereshetünk ``egy súlyos halmazt'' a mohó algoritmussal.

Mondjuk ki azt a tételt, amely megmondja mikor adja meg a fenti eljárás (tetszőleges súlyfüggvény esetén) az optimális halmazt halmazrendszerünkből.

Bizonyítsuk be, hogy feltételünk nem teljesülése esetén alkalmas súlyfüggvény ``becsapja '' a mohó algoritmust.

2') Írjuk le, egy tartalmazásra nézve zárt H halmazrendszer (ha H egy A eleme és B részhalmaza A-nak, akkor B is H-nak eleme) és az alaphalmazon adott súlyfüggvény (amely a halmazokhoz is súlyt rendel) esetén hogyan kereshetünk ``egy súlyos halmazt'' a mohó algoritmussal.

Adjon egy konkrét példát. Majd futassa rajta a mohó algoritmust. Példáját úgy adja meg, hogy a futás eredménye ne legyen optimális.

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 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ám nem érdekelt minket, ez a kis plusz sok diákot megzavar a fenti kérdés megválaszolásában.

4) 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.

Tegyük fel, hogy F egy komponensébe eső két külső pont között vezet él és az ez által ``előidézett'' kört zsugorítjuk. Igaz-e, hogy az F erdő képe a zsugorítás után sem bővíthető? Válaszunkat indokoljuk (igen válasz esetén állításunkat bizonyítsuk be, nem válasz esetén adjunk egy példát ami mutatja válaszunk helyességét).

Ismét tegyük fel, hogy F egy komponensébe eső két külső pont között vezet él és az ez által ``előidézett'' kört zsugorítjuk. Miért lesz az M párosítás zsugorítás utáni képe párosítás?

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

Tegyük fel, hogy F külső pontjai között nem vezet él. Indokoljuk miért optimális a párosításunk.

Megjegyzés: 4) és 4') két nehéz feladatnak tűnik. Nem azok. Az utolsó részkérdések egy egyszerű példával, egy-két mondattal megválaszolhatók. Aki a magyar módszert és ebből Edmonds-algoritmus vázlatos elmondásának elejét jól megértette, azok számára nem probléma.

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

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