COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Tranzitív lezárt


Ignore:
Timestamp:
07/02/10 23:24:58 (12 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Tranzitív lezárt

    v1 v1  
     1= Tranzitív lezárt =
     2
     3Hatékony algoritmus implementálása egy gráf tranzitív lezártjának előállítására.
     4
     5== Háttér ==
     6
     7Egy ''G''=(''V'',''E'') irányított gráf tranzitív lezártja az a ''G' ''=(''V'',''E' '') gráf, amelyben ''u''-ból ''v''-be pontosan akkor vezet él, ha ''u''-ból vezet irányított út ''v''-be az eredeti ''G'' gráfban.
     8
     9Egy gráf tranzitív lezártja könnyen kiszámítható pl. a Floyd-Warshall-algoritmussal O(''n''^3^) időben, illetve ''n'' szélességi kereséssel O(''n''(''n''+''m'')) időben. Ugyanakkor vannak lényegesen hatékonyabb módszerek is, amelyek a gyakorlatban majdnem lineáris időben futnak.
     10
     11Egy ilyen módszer az erősen összefüggő komponensek meghatározásán, valamint a komponensek gráfjának topologikus rendezésén alapul, de összetett adatszerkezeteket is alkalmaz. További információ:
     12[http://www.cs.hut.fi/~enu/thesis.html]
     13
     14== Feladat ==
     15
     16A feladat minél hatékonyabb algoritmusok implementálása, valamint a különböző módszerek összehasonlítása.
     17
     18A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     19
     20'''Kapcsolódó ticketek:''' #378.
     21
     22== Előfeltételek ==
     23
     24 - C++ programozási nyelv ismerete
     25 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     26 - angol nyelvismeret