= Irányított gráf erősen összefüggővé tétele =

Egy algoritmus implementálása, amely egy irányított gráfot minimális számú él összehúzásával erősen összefüggővé tesz.

== Háttér ==

Legyen ''D''=(''V'',''A'') egy gyengén összefüggő irányított gráf (digráf). Legyen ''X'' a ''V'' egy részhalmaza, amelyből nem vezet ki él. Ekkor ''X''-et ''magnak'' nevezzük, és ha az ''X'' magba lép be él, akkor belépő élek halmazát nevezzük ''egyirányú'' (vagy ''irányított'') ''vágásnak''. ''D'' nyilván pontosan akkor erősen összefüggő, ha nem létezik egyirányú vágás.

A ''D'' éleinek egy ''F'' részhalmazát nevezzük ''irányított kötésnek'' (röviden ''kötésnek''), ha ''F'' elemeinek összehúzása erősen összefüggő digráfot eredményez. Ez nyilván ekvivalens azzal, hogy ha ''F'' elemeit megfordítva hozzáadjuk ''D''-hez, akkor erősen összefüggő digráfot kapunk. Könnyen látható az is, hogy egy ''F'' élhalmaz pontosan akkor kötés, ha minden egyirányú vágást lefog (vagyis minden egyirányú vágásnak tartalmazza legalább egy elemét).

A ''Lucchesi-Younger-tétel'' szerint egy gyengén összefüggő digráfban a minimális kötés elemszáma egyenlő az éldiszjunkt egyirányú vágások maximális számával. A tételnek létezik algoritmikus bizonyítása is, amely megfogalmaz egy összetett, de polinomiális idejű algoritmust, amellyel meghatározható egy minimális elemszámú ''F'' irányított kötés, valamint |''F''| éldiszjunkt egyirányú vágás.

A problémának költséges változatát is vizsgálhatjuk, vagyis amikor egy minimális költségű kötést keresünk. Ehhez azonban már a szubmoduláris folyamok elméletére van szükség.

== Feladat ==

A Lucchesi-Younger-tétel bizonyításához használt algoritmus implementálása minimális elemszámú irányított vágás keresésére. Különböző javítási lehetőségek, heurisztikák keresése és tesztelése.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

== Előfeltételek ==

 - C++ programozási nyelv ismerete
 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
 - angol nyelvismeret