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