COIN-OR::LEMON - Graph Library

Gráfosztályok előállítása konstruktív karakterizáció segítségével

Algoritmus kifejlesztése bizonyos gráfosztályokba tartozó összes n csúcsú gráf felsorolására (generálására).

Háttér

Egy P gráfosztály konstruktív karakterizációja alatt egy olyan eljárást értünk, amely P kisszámú eleméből néhány egyszerű lépés segítségével előállítja P összes elemét. Egyszerű példa a 2-összefüggő gráfok ún. fülfelbontása.

A Gráfelméleti sejtés-ellenőrző modul fejlesztése feladathoz kapcsolódóan fontos lehet például az összes n csúcsú k-élösszefüggő gráf végignézése. Ennek az osztálynak ismert egy egyszerű konstruktív karakterizációja, melynek segítségével sok nagyságrenddel gyorsabban elvégezhető a feladat, mintha nyers erővel megvizsgálnánk az összes lehetséges n csúcsú részgráfot, és kiválasztanánk közülük a k-élösszefüggőeket.

Feladat

A feladat egy általános modul fejlesztése, amely képes egy gráfosztály összes elemét felsorolni. Mind önmagában, mind a Gráfelméleti sejtés-ellenőrző modul fejlesztése témával kombinálva végezhető.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is 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
Last modified 8 years ago Last modified on 11/23/09 17:31:17