Gráfok direkt szorzata

Gráfok direkt szorzatát megvalósító adatstrukúra implementálása.

Háttér

Egy G1=(V1,E1) és egy G2=(V2,E2) gráf direkt szorzatán a

G1xG2 := (V1xV2, {((u1,u2),(v1,v2)) : (u1,v1) éle G1-nek és (u2,v2) éle G2-nek})

grá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.

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ő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.

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.

Előfeltételek

• C++ programozási nyelv ismerete
• alap gráfelméleti ismeretek
• angol nyelvismeret