COIN-OR::LEMON - Graph Library

Changes between Version 5 and Version 6 of Gráfok direkt szorzata


Ignore:
Timestamp:
05/25/10 16:00:58 (9 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Gráfok direkt szorzata

    v5 v6  
    1111grá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.
    1212
     13Grá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.
     14 - http://en.wikipedia.org/wiki/Cartesian_product_of_graphs
     15 - http://en.wikipedia.org/wiki/Tensor_product_of_graphs
     16 - http://en.wikipedia.org/wiki/Lexicographical_product_of_graphs
     17 - http://en.wikipedia.org/wiki/Modular_product_of_graphs
     18 - http://en.wikipedia.org/wiki/Rooted_product_of_graphs
     19
    1320== Feladat ==
    1421
    1522A 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.
    1623
    17 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 é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.
     24A 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.
    1825
    1926Cé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.