COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
03/26/09 16:09:07 (12 years ago)
Author:
veghal
Comment:

--

Legend:

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

    v1 v1  
     1== Gráfosztályok előállítása konstruktív karakterizáció segítségével ==
     2
     3Egy szubrutin kifejlesztése bizonyos gráfosztályokba tartozó összes ''n'' csúcsú gráf felsorolására.
     4
     5=== Háttér ===
     6Egy ''P'' gráfosztály konstruktív karakterizációja alatt egy olyan eljárást értünk, amely ''P'' kisszámú eleméből
     7né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.
     8
     9A [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ú
     10''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
     11sok nagyságrenddel gyorsabban elvégezhető a feladat, mintha nyers erővel megvizsgálnánk az összes lehetséges ''n'' csúcsú részgráfot,
     12és kiválasztanánk közülük a ''k''-élösszefüggőeket.
     13
     14=== Feladat ===
     15A feladat egy általános modul fejlesztése, amely képes egy gráfosztály összes elemét felsorolni.
     16Mind önmagában, mind a [wiki:"Gráfelméleti sejtés-ellenőrző modul fejlesztése"] témával kombinálva végezhető.
     17A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     18
     19=== Előfeltételek ===
     20
     21 - C++ programozási nyelv ismerete
     22 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     23 - angol nyelvismeret