Changes between Initial Version and Version 1 of Élgráf adatstruktúra

Timestamp:

11/23/09 15:35:21 (15 years ago)

Author:

Peter Kovacs

Comment:

--

Élgráf adatstruktúra

@@ +1 @@
+= Élgráf adatstruktúra =
+
+Egy irányítatlan gráf élgráfját megvalósító dinamikus adatstruktúra implementálása.
+
+== Háttér ==
+
+Egy ''G'' irányítatlan gráf ''L''(''G'') élgráfja a ''G'' gráf éleinek kapcsolatát reprezentálja.
+''L''(''G'') egy egyszerű irányítatlan gráf, amelynek csúcsai a ''G'' élei, és két csúcsot pontosan akkor köt össze él, ha az eredeti gráfban a két él szomszédos (van közös végpontjuk).
+
+Ez a struktúra fontos fontos szerepet tölt be a gráfelméletben és gyakorlati alkalmazásai is vannak.
+További információ: [http://en.wikipedia.org/wiki/Line_graph].
+
+== Feladat ==
+
+A LEMON könyvár nagy erőssége, hogy lehetővé teszi algoritmusok futtatását "implicit gráfokon", vagyis olyan strukturákon, amelyek nincsenek fizikailag eltárolva a memóriában.
+
+A jelentkező feladata egy olyan LEMON gráf adatstruktúra implementálása, amely ''dinamikus'' módon előállítja egy gráf élgráfját és lehetővé teszi algoritmusok futtatását a kapott gráfon. A "dinamikus" működés azt jelenti, hogy az alapgráf megváltoztatásakor automatikusan megváltozik az élgráf is.
+
+Cél, hogy erre a feladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba.
+
+A feladat elsősorban nagyprogram alapjául szolgálhat. A célként kitűzött adatstruktúra implementálása kiváló lehetőséget biztosít a LEMON programkönyvtár koncepciójának és felépítésének alapos megismerésére; ez a tudás késöbbiekben alapja lehet egy értékes TDK-, ill. diplomamunkának is.
+
+'''''Megjegyzés:''' A téma összevonható egy másik hasonló feladattal: [wiki:"Gráfok direkt szorzata"]''.
+
+== Előfeltételek ==
+
+ - C++ programozási nyelv ismerete
+ - alap gráfelméleti ismeretek
+ - angol nyelvismeret