Changes between Initial Version and Version 1 of Irányított gráf erősen összefüggővé tétele

Timestamp:

09/22/09 15:15:10 (15 years ago)

Author:

Peter Kovacs

Comment:

--

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

@@ +1 @@
+= 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 szakdolgozat, nagyprogram é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