= 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