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

Timestamp:

07/02/10 21:24:58 (15 years ago)

Author:

Peter Kovacs

Comment:

--

Tranzitív lezárt

@@ +1 @@
+= 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