Mit jelent a tranzitív lezárt?

"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(n3) 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."