= Tranzitív lezárt =

Hatékony algoritmus implementálása egy gráf tranzitív lezártjának előállítására.

== Háttér ==

Egy ''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.

Egy 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.

Egy 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ó:
[http://www.cs.hut.fi/~enu/thesis.html]

== Feladat ==

A feladat minél hatékonyabb algoritmusok implementálása, valamint a különböző módszerek összehasonlítása.

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

'''Kapcsolódó ticketek:''' #378.

== Előfeltételek ==

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