Changes between Initial Version and Version 1 of Gráfosztályok előállítása konstruktív karakterizáció segítségével

Timestamp:

03/26/09 15:09:07 (16 years ago)

Author:

veghal

Comment:

--

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

@@ +1 @@
+== Gráfosztályok előállítása konstruktív karakterizáció segítségével ==
+
+Egy szubrutin kifejlesztése bizonyos gráfosztályokba tartozó összes ''n'' csúcsú gráf felsorolá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 [wiki:"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 [wiki:"Gráfelméleti sejtés-ellenőrző modul fejlesztése"] témával kombinálva végezhető.
+A feladatkör szakdolgozat, nagyprogram é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