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