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