Hujter Bálint: Vágás-ekvivalens irányított gráfok

Adott egy irányított gráf. Ha egy vágás összes éle egy irányba mutat, akkor ezek irányítását együtt megfordíthatjuk. Speciálisan egy nyelőpont forrássá alakítható és viszont. El lehet-e érni ilyen lépésekkel, hogy a csúcsok befokai egy adott g:V \to N korlát alá kerüljenek? Erre a feladatra adunk algoritmust. Kielemezzük, hogy min múlik, ha nem lehet g alatti irányítást elérni. Bemutatjuk a probléma kapcsolatait a chip-firing játékkal és más irányításokkal kapcsolatos eredményekkel.