= Gráfok direkt szorzata =

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

== Háttér ==

Egy ''G'',,1,,=(''V'',,1,,,''E'',,1,,) és egy ''G'',,2,,=(''V'',,2,,,''E'',,2,,) gráf direkt szorzatán a

  ''G'',,1,,x''G'',,2,, := (''V'',,1,,x''V'',,2,,, {((''u'',,1,,,''u'',,2,,),(''v'',,1,,,''v'',,2,,)) : (''u'',,1,,,''v'',,1,,) éle ''G'',,1,,-nek és (''u'',,2,,,''v'',,2,,) éle ''G'',,2,,-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.

Gráfok másféle szorzatait is szokták vizsgálni, amelyknél a csúcshalmaz szintén ''V'',,1,,x''V'',,2,,, de az élek halmazát eltérő módon definiálják. Ezeknek különböző gyakorlati alkalmazásai vannak.
 - http://en.wikipedia.org/wiki/Cartesian_product_of_graphs
 - http://en.wikipedia.org/wiki/Tensor_product_of_graphs
 - http://en.wikipedia.org/wiki/Lexicographical_product_of_graphs
 - http://en.wikipedia.org/wiki/Modular_product_of_graphs
 - http://en.wikipedia.org/wiki/Rooted_product_of_graphs

== 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 két gráf direkt szorzatát (illetve egyéb szorzatgráfokat) é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 BSc szakdolgozat 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:"Élgráf adatstruktúra"]''.

== Előfeltételek ==

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