COIN-OR::LEMON - Graph Library

Version 1 (modified by Peter Kovacs, 14 years ago) (diff)

--

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ó:

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