COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Gráfok direkt szorzata


Ignore:
Timestamp:
06/17/09 12:20:21 (11 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Gráfok direkt szorzata

    v1 v1  
     1= Gráfok direkt szorzata =
     2
     3Gráfok direkt szorzatát megvalósító adatstrukúra implementálása.
     4
     5== Háttér ==
     6
     7Egy ''G1''=(''V1'',''E1'') és egy ''G2''=(''V2'',''E2'') gráf direkt szorzatán a
     8
     9  ''G1''x''G2'' := (''V1''x''V2'', {((''u1'',''u2''),(''v1'',''v2'')) : (''u1'',''v1'') éle ''G1''-nek és (''u2'',''v2'') éle ''G2''-nek})
     10
     11gráfot értjük. E gráfok fontos szerepet töltenek be a gráfelméletben, de gyakorlati alkalmazásuk is van, például a grid hálózatok terén.
     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ők feladata egy olyan LEMON gráf adatstruktúra implementálása, amely ''dinamikus'' módon előállítja két gráf direkt szorzatát és lehetővé teszi algoritmusok futtatását a kapott gráfon. A "dinamikus" működés azt jelenti, hogy az alapgráfok megváltoztatásakor automatikusan megváltozik a direkt szorzat 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== Előfeltételek ==
     24
     25 - C++ programozási nyelv ismerete
     26 - alap gráfelméleti ismeretek
     27 - angol nyelvismeret