= 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ő.

== Előfeltételek ==

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