Fák pakolása, fedés fákkal

Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés).

Háttér

A pakolási feladat így hangzik: adott egy összefüggő irányítatlan gráf és egy k pozitív egész, döntsük el, hogy létezik-e a gráfban k darab páronként éldiszjunkt feszítőfa. A szükséges és elégséges feltételt Tutte egy tétele szolgáltatja. A kérdés a matroid-partíciós feladat speciális esete.

A fedési feladat bemenete ugyanaz, mint a pakolási feladaté, de a kérdés az, hogy a gráf élei lefedhetők-e k feszítőfával (illetve mondhatnánk erdőt is, a többszörösen fedett élek kihagyásával). Az elméleti választ Nash-Williams tétele adja meg nekünk egy ritkasági feltétel formájában.

Feladat

A pakolási és a fedési feladat elméletének és a megoldó algoritmusoknak a megismerése, majd ezek némelyikének az implementálása, hatékonyságuk összehasonlítása, heurisztikus javítások keresése.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is. Az is elképzelhető, hogy a két feladat közül csak az egyiket dolgozza fel a jelentkező.

Megjegyzés: A témakörrel már foglalkozott egy vagy több szakdolgozó, ezért a részletekről mindenképpen érdemes érdeklődni.

Előfeltételek

• C++ programozási nyelv ismerete
• gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
• angol nyelvismeret