COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
11/23/09 16:35:21 (10 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Élgráf adatstruktúra

    v1 v1  
     1= Élgráf adatstruktúra =
     2
     3Egy irányítatlan gráf élgráfját megvalósító dinamikus adatstruktúra implementálása.
     4
     5== Háttér ==
     6
     7Egy ''G'' irányítatlan gráf ''L''(''G'') élgráfja a ''G'' gráf éleinek kapcsolatát reprezentálja.
     8''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).
     9
     10Ez a struktúra fontos fontos szerepet tölt be a gráfelméletben és gyakorlati alkalmazásai is vannak.
     11További információ: [http://en.wikipedia.org/wiki/Line_graph].
     12
     13== Feladat ==
     14
     15A 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.
     16
     17A 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.
     18
     19Cé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.
     20
     21A 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.
     22
     23'''''Megjegyzés:''' A téma összevonható egy másik hasonló feladattal: [wiki:"Gráfok direkt szorzata"]''.
     24
     25== Előfeltételek ==
     26
     27 - C++ programozási nyelv ismerete
     28 - alap gráfelméleti ismeretek
     29 - angol nyelvismeret