Gráfelméleti sejtés-ellenőrző modul fejlesztése

Egy 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.

Háttér

Gyakori 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őrizni lehetne.

A 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. Konkrét példaként álljon itt az ​EGRES csoport honlapján a nyitott kérdések közül a 12., 16. és 27.

Feladat

Legelső 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ó. Amennyiben 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 (ld. pl. Gráfosztályok előállítása konstruktív karakterizáció segítségével).

A 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. 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