COIN-OR::LEMON - Graph Library

Version 6 (modified by Peter Kovacs, 14 years ago) (diff)

--

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örön már dolgozott/dolgozik szakdolgozó, ezért a részletekről érdemes érdeklődni.

Előfeltételek

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