COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Gráfizomorfizmus, részgráfizomorfizmus


Ignore:
Timestamp:
08/02/10 13:39:55 (12 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Gráfizomorfizmus, részgráfizomorfizmus

    v1 v1  
     1= Gráfizomorfizmus, részgráfizomorfizmus =
     2
     3Heurisztikus és egzakt algoritmusok implementálása a gráfizomorfizmus és részgráfizomorfizmus problémára.
     4
     5== Háttér ==
     6
     7A gráfizomorfizmus az egyik legismertebb gráfelméleti probléma, amelynek számos alkalmazása van. Algoritmikus szempontból nehéz és sokat vizsgált feladat, de a pontos bonyolultságelméleti státusza máig nyitott kérdés (nem bizonyított sem az, hogy polinomiális, sem pedig az, hogy NP-teljes). Számos különböző algoritmus született a feladat egzakt, illetve közelítő megoldására általános és speciális gráfokra egyaránt (pl. síkgráfok, fokszámkorlátos gráfok, színezett gráfok stb.).
     8
     9A részgráfizomorfizmus probléma a gráfizomorfizmus általánosítása: azt kell eldöntenünk, hogy egy gráf tartalmaz-e egy másik gráffal izomorf részgráfot. Ez a feladat már biztosan NP-teljes, nyilvánvalóan általánosítása a Hamilton-kör és a maximális klikk problémáknak is.
     10
     11További információ:
     12  - [http://en.wikipedia.org/wiki/Graph_isomorphism]
     13  - [http://en.wikipedia.org/wiki/Graph_isomorphism_problem]
     14  - [http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem]
     15
     16== Feladat ==
     17
     18A feladat a témakörben született, gyakorlatban is hatékony algoritmusok áttekintése, valamint néhány kiválasztott módszer implementálása a gráfizmorfizmus és részgráfizomorfizmus probléma általános, illetve esetleg speciális változataira.
     19
     20A feladatkör elsősorban MSc szakdolgozat és TDK alapjául szolgálhat, akár több jelentkező számára is.
     21
     22== Előfeltételek ==
     23
     24 - C++ programozási nyelv ismerete
     25 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     26 - angol nyelvismeret