1) Definiálja a séta, vonal fogalmát. Rajzoljon fel egy gráfot benne egy sétát, ami nem vonal és (mellette) egy sétát, ami vonal.
Írja fel a mohó vonalnövelés algoritmusát.
Mit mondhatunk a fenti algoritmus elakadásának pontjáról? Indokolja is válaszát.
Definiálja az Euler-vonal fogalmát. Mondjon szükséges és elégséges feltételt arra, hogy egy gráfban legyen NEM záródó Euler-vonal.
2) 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.
3) Definiálja egy gráf jó színezésének fogalmát. Milyen optimalizálási problémát vizsgáltunk ezzel kapcsolatban?
Írja le a mohó színezési algoritmus azon változatát, amely alapján definiálható khimohó,π. Definiálja is az utóbbi fogalmat.
Hogyan válasszuk a mohó algoritmus π sorrendjét, ha összefüggő, nem reguláris gráfot színezünk mohó módon?
Igazolja, hogy a fent leírt sorrend létezik. Írjon le egy eljárást megkeresé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.