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 a hálózat, folyam, folyam értékének fogalmát.
Írja le mit értünk a folyamra vonatkozó javító úton és indokolja miért használjuk rá javító jelzõt.
Írja le hogyan kerestünk maximális értékû folyamot egy adott hálózatban.
Indokolja, ha minden él kapacitása 1, akkor az eljárás leáll és mondja meg mit tudhatunk az output-folyam által az egyes élekhez rendelt számokról.
1) Mondja ki Menger tételét (éldiszjunkt utak irányított gráfban).
A Menger-tétel gráfjában minden él kapacitása legyen 1 (a tétel két kitüntetett csúcs lesz a forrás és nyelõ). Az így kapott hálózatban mi lesz a legkisebb vágáskapacitás? Indokolja válaszát.
Az így kapott hálózatban mi lesz a legnagyobb folyamérték? Indokolja válaszát.
Írja fel a maximális-folyam-minimális-vágás tételét.
2) 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.)
2) 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).
2) Definiálja egy gráf derékbõségét.
Lehet-e egy 10-szeresen összefüggõ gráf derékbõsége 1000?
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.
3) 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.
3) Mondja ki a Ramsey-tételt (kétszínû, gráf változat), Schur-tételt és van der Waerden tételét.
Melyik esetekben igaz, hogy a színezett struktúrának megadható konstans hányada úgy, hogy a monokromatikusan keresett rész ne forduljon elõ benne? Indokolja válaszát.
Definiálja az Erdõs-Turán-féle rk(n) függvényt.
Mondja ki a Szemerédi-tételt.
3) Hogyan mértük, hogy egy tetszõleges gráf mennyire van távol a síkgráfoktól?
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 Kn metszési számának nagyságrendje (mint n függvénye)? Indokolja válaszát alsó és felsõ becsléssel.
4) 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.
4) 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.
4) Í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?
4) Definiálja egy egyszerû gráf sajátértétekeit.
Mit mondhatunk a legnagyobb sajátértékrõl? Igazolja is ezt.
Mondja ki Hoffman tételét.
Adjon egy színezési algoritmust, amely a tételt "bizonyítja". Igazolja is az algoritmus analízisét.