1) Definiálja egy hurokélnélküli G gráf pont-él-illeszkedési mátrixát. Írja le, hogyan változik a definíció, ha alapgráfunk irányított.

Dolgozzunk irányított gráfokkal. Mit tud mondani a pont-él-illeszkedési mátrix rangjáról? Bizonyítson be egy felső becslést összefüggő gráfokra.

Mondja ki a Kirchoff-tételt.

Mondja ki a Cayley-tételt.

Cayley tételét kombinatorikusan is bizonyítottuk. Az ebben szereplő bijekció és inverze közül az egyiket írja le.

1) Definiálja egy páros gráf szomszédsági mátrixát.

Definiálja egy négyzetes mátrix permanensét.

Milyen kapcsolat van egy páros gráf szomszédsági mátrixának permanense és a gráfbeli párosít'asok között. Indokolja válaszát.

Írjon le egy véletlen algoritmust annak tesztelésére, hogy egy páros gráfban van-e teljes párosítás.

Mondja ki azt a tételt, amley alapján becsülhető a hibázás valószínűsége.

A tétel alapján adjon módszert az algoritmusának hibázási valószínűségének csökkentésére.

1) Definiálja mikor nevezünk egy ponthalmazt Tutte-akadálynak.

Indokolja meg mit akadályoz meg egy Tutte-akadály léte.

Legyen T egy Tutte-akadály. Írjon fel egy becslést a legnagyobb párosítás méretére T függvényében.

Futassa az Edmonds-algoritmust egy M párosítással. Tegyük fel, hogy zsugorítás nélkül, sikertelen kereséssel leáll az algoritmus. Bizonyítsa be, hogy a párosítás optimális.

1) Írja le a javító út (egy párosításra nézve) fogalmát. Indokolja meg, miért kapta a javító jelzőt.

Adott egy gráf és benne egy párosítás. Írja le hogyan kerestünk mohó módon javító utakat.

Adjon példát, amikor amohó eljárás nem talál javító utat, pedig van a gráfban.

Páros gráfon futassa a fenti algoritmust, ami sikertelen kereséssel áll le. A futás alapján mutassan a párosítással azonos méretű lefogó ponthalmazt a páros gráfban. Mi következik ebből?

1) Definiálja a k-szorosan összefüggő és k-szorosan élösszefüggő gráf fogalmát.

Definiálja egy ponthalmaz él-határát. A fenti fogalmak melyike fogalmazható át ezzel a fogalommal és hogyan?

A k-szorosan összefüggő és k-szorosan élösszefüggő fogalmak közül melyik fogalomból következik a másik? A következést igazolja, a nem következést egy példával illusztrálja.

1) Definiálja a Hajós tételhez szükséges operációkat.

Igazolja, hogy, ha nem-k-színezhető gráfokra alkalmazza, akkor az eredmény is nem-k-szinezhető lesz.

Mondja ki Hajós tételét. Két iránya közül melyik a nehéz, melyik az egyszerű.

Mondja ki Hajós tételét nem-2-színezhető gráfokra. Igazolja nehéz irányát. (Ami nem annyira nehéz.)

1) Definálja egy gráf élszínezését, jó élszínezését és írja le milyen optimalizálási kérdést vizsgáltunk erre vonatkozólag.

Milyen kapcsolatban áll az élkromatikus szám a maximális fokszámmal. (Mondjon ki becsléseket és az egyszerű oldalt igazolja.) Írjon le egy gráf osztályt ahol könnyű megmondani, hogy az alsó és felső becslés közül melyik a korrekt.

Vizing-tétel bizonyításában egy (parciális) élszínezést átszíneztünk, majd kiterjesztettük a színezést. Írja le, hogyan színeztünk át (az élek, színek választására nem vagyok kiváncsi).

1) Definiálja egy gráf derékbőségét.

Egy n elemű csúcshalmazon véletlen gráfot generálunk: Minden csúcspárra - függetlenül - p valószínűséggel összekötjük őket (1-p valószínűséggel nem lesznek összekötöttek). A legnagyobb független ponthalmaz mérete egy valószínűségi változó. Becsülje meg várható értékét.

A legnagyobb független halmaz mérete mit mond a gráf kromatikus számáról? Indokolja válaszát.

2) Definiálja mikor nevezünk egy gráfot síkgráfnak.

Vegyünk fel három diszjunkt háromszöget, majd egy új (tizedik) csúcsot, amit kössünk össze egy-egy ponttal mindegyik háromszögről. Síkgráfot kaptunk-e? Ha nem, indokoljuk meg miért. Ha igen, akkor rajzoljuk le szépen, azonosítsuk tartományait, a tartományok határának hosszait írjuk fel.

Definiálja a minor és topologikus részgráf fogalmát.

Igazolja, hogy a Petersen-gráf nem síkgráf. Indoklásában a hivatkozott állításokat részletesen fejtse ki.

Mondja ki Kuratowski és Wagner tételét és azonsítsa és indokolja a két tétel egyszerű irányát.

2) Definiálja egy egyszerű gráf metszési számát.

A metszési szám paraméterre két becslést adtunk. Mondja ki is bizonyítsa be az egyszerűbbet.

Mondja ki a bonyolultabb becslést.

Bizonyítsa is be ezt.

Mi a K_n metszési számának nagyságrendje (mint n függvénye)? Indokolja válaszát alsó és felső becsléssel.

2) Definiálja a Turán-gráfokat.

Definiálja az ext(n;T) jelölést.

Becsülje az ext(n;T) függvényt ha T fa. Indokolja becslését, ha T egy négy pontú út.

Becsülje az ext(n;T) függvényt ha T a Petersen-gráf.

Mondja ki milyen becslésekre emlékszik ext(n;C₄) függvényre.

2) Mondja ki a Ramsey-tételt (kétszínű, hármasokra vonatkozó változatot, illetve a háromszínű, gráfokra vonatkozó változatot),

Egyiket igazolja is.

Mondja ki az Erdős-Szekeres tételt.

Igazolja is a Ramey-tétel megfelelő változatából.

2) Egy halmazrendszert mikor nevezünk Sperner-rendszernek?

Adjon példát Sperner-rendszerekre.

Mondja ki a Sperner-tételt.

Mondja ki a LYM egyenlőtlenséget.

Indokolja meg miért következik a LYM egyenlőtlenségből a Sperner-tétel.

Igazolja a LYM egyenlőtlenséget.

2) Mikor nevezünk egy halmazrendszert metszőnek.

Adjon példát metsző halmazrendszerre.

Milyen sok éle lehet egy n elemű alaphalmaz feletti metsző halmazrendszernek? Indokolja válaszát.

Mondja ki az Erdős-Ko-Rado-tételt.

Indokolja a tételt.