COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Gráfelméleti sejtés-ellenőrző modul fejlesztése


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

--

Legend:

Unmodified
Added
Removed
Modified
  • Gráfelméleti sejtés-ellenőrző modul fejlesztése

    v1 v1  
     1== Gráfelméleti sejtés-ellenőrző modul fejlesztése ==
     2
     3Egy olyan általános keretrendszer kidolgozása, amely kisméretű példák ellenőrzésével segíti a gráfelméleti kutatók munkáját.
     4
     5=== Háttér ===
     6
     7Gyakori eset, hogy a gráfelméleti területen dolgozó kutató hosszú hónapokig dolgozik egy sejtés bizonyításán, melyre végül egy tíznél kevesebb pontú gráfot talál ellenpéldaként. Munkájukat nagyban segítené, ha bizonyos sejtéseket kisméretű gráfokon ellenőrízni lehetne.
     8
     9A kérdéseket ilyen típusú sémák írnák le: igaz-e, hogy minden (legfeljebb) ''n'' csúcsú, a ''P'' tulajdonságot kielégítő gráfra teljesül a ''Q'' tulajdonság? Vagy: mennyi a (legfeljebb) ''n'' csúcsú, ''P'' tulajdonságú gráfok száma? Ugyanezek a kérdések elképzelhetőek egy adott gráf részgráfjaira vonatkozóan is.
     10 
     11Konkrét példaként álljon itt az [http://www.cs.elte.hu/egres EGRES csoport honlapján] a nyitott kérdések közül a 12., 16. és 27.
     12
     13=== Feladat ===
     14Legelső közelítésben kidolgozandó egy olyan eljárás, mely az ''n'' ponton lehetséges összes gráfot végignézi, és közülük kiválasztja a ''P'' tulajdonsággal rendelkezőeket. A módszer hátránya, hogy csak nagyon kicsi gráfok esetére alkalmazható.
     15Amennyiben ''P'' monoton gráftulajdonság (mint pl. az összefüggőség, ahol egy összefüggő gráfhoz további éleket adva is összefüggő gráfot kapunk), akkor egy kicsit hatékonyabban tudjuk végignézni őket. Még többet javíthatunk, ha van egy hatékony szubrutinunk a ''P'' tulajdonságú gráfok felsorolására
     16(ld. pl. [wiki:"Gráfosztályok előállítása konstruktív karakterizáció segítségével"]).
     17
     18A feladat lehet mind az általános szubrutin, mind szűkebb osztályokra való implementálása, illetve konkrét problémákra való hatékony megvalósítása.
     19A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     20
     21=== Előfeltételek ===
     22
     23 - C++ programozási nyelv ismerete
     24 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     25 - angol nyelvismeret