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

Timestamp:

08/02/10 13:39:55 (15 years ago)

Author:

Peter Kovacs

Comment:

--

Gráfizomorfizmus, részgráfizomorfizmus

@@ +1 @@
+= Gráfizomorfizmus, részgráfizomorfizmus =
+
+Heurisztikus és egzakt algoritmusok implementálása a gráfizomorfizmus és részgráfizomorfizmus problémára.
+
+== Háttér ==
+
+A 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.).
+
+A 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.
+
+További információ:
+  - [http://en.wikipedia.org/wiki/Graph_isomorphism]
+  - [http://en.wikipedia.org/wiki/Graph_isomorphism_problem]
+  - [http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem]
+
+== Feladat ==
+
+A 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.
+
+A feladatkör elsősorban MSc szakdolgozat és TDK alapjául szolgálhat, akár több jelentkező számára is.
+
+== Előfeltételek ==
+
+ - C++ programozási nyelv ismerete
+ - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
+ - angol nyelvismeret