COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
09/22/09 17:15:10 (10 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Irányított gráf erősen összefüggővé tétele

    v1 v1  
     1= Irányított gráf erősen összefüggővé tétele =
     2
     3Egy 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.
     4
     5== Háttér ==
     6
     7Legyen ''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.
     8
     9A ''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).
     10
     11A ''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.
     12
     13A 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.
     14
     15== Feladat ==
     16
     17A 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.
     18
     19A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     20
     21== Előfeltételek ==
     22
     23 - C++ programozási nyelv ismerete
     24 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     25 - angol nyelvismeret