Changes between Version 1 and Version 2 of Fák pakolása, fedés fákkal
- Timestamp:
- 06/17/09 10:35:33 (15 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Fák pakolása, fedés fákkal
v1 v2 1 = = Fák pakolása, fedés fákkal ==1 = Fák pakolása, fedés fákkal = 2 2 3 Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés) 3 Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés). 4 4 5 == = Háttér ===5 == Háttér == 6 6 7 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 7 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. 8 8 9 A ''fedési feladat'' bemenete ugyanaz, mint a pakolási feladaté, de a kérdés az, hogy a gráf élei lefedhetők 9 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. 10 10 11 == = Feladat ===11 == Feladat == 12 12 13 13 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. … … 16 16 Az is elképzelhető, hogy a két feladat közül csak az egyiket dolgozza fel a jelentkező. 17 17 18 == = Előfeltételek ===18 == Előfeltételek == 19 19 20 20 - C++ programozási nyelv ismerete
