1) Definiálja a következő fogalmakat: folyam, folyam értéke.
Írja le, mit értünk a folyamra vonatkozó javító úton. Miért használjuk rá a ``javító'' jelzőt?
Írja le, hogyan kerestünk maximális értékű folyamot egy adott hálózatban.
Indokolja meg, miért áll meg az eljárás, ha minden él kapacitása egységnyi. Mit mondhatunk el a kimenet folyama által az egyes élekhez rendelt számokról?
2) Definiálja, mikor nevezünk egy ponthalmazt Tutte-akadálynak.
Indokolja meg, mit akadályoz meg egy Tutte-akadály léte.
Legyen G(A,B) egy k-reguláris, egyszerű páros gráf. Lássa be, hogy G-ben van teljes párosítás.
Írja le, hogyan kerestünk teljes párosítást páros gráfokban véletlen algoritmus segítségével.
3) Mit jelent a Hamilton-kör fogalma?
Tegyük fel, hogy G-ben van Hamilton-kör. Mit mondhatunk G csúcs-összefüggőségéről?
Adjon meg egy n csúcsú egyszerű gráfot, melyben a minimális fok (n/2)-1, és nincsen benne Hamilton-kör. Mit mondhatunk akkor, ha minimális fok eléri n/2-őt?
Mondja ki Chvatal tételét (a fokszámsorozatos tétel).
4) Hogyan definiáljuk egy gráf sajátértékeit és sajátvektorait?
Mit jelent az, hogy G egy (n,d,c)-expander?
Legyen G egy n csúcsú, d-reguláris egyszerű gráf, melyben a második legnagyobb sajátérték p. Vágjuk ketté G csúcshalmazát a B és C nemüres halmazokra. Mit mondhatunk a B és C között menő élek számáról?
Lássuk be, hogy az előző kérdés feltételeinek teljesülése esetén G egy (n,d,(d-p)/(2d))-expander.