COIN-OR::LEMON - Graph Library

Changes between Version 1 and Version 2 of Fák pakolása, fedés fákkal


Ignore:
Timestamp:
06/17/09 10:35:33 (10 years ago)
Author:
Peter Kovacs
Comment:

--

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 =
    22
    3 Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés)
     3Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés).
    44
    5 === Háttér ===
     5== Háttér ==
    66
    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.
     7A ''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.
    88
    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.
     9A ''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.
    1010
    11 === Feladat ===
     11== Feladat ==
    1212
    1313A 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.
     
    1616Az is elképzelhető, hogy a két feladat közül csak az egyiket dolgozza fel a jelentkező.
    1717
    18 === Előfeltételek ===
     18== Előfeltételek ==
    1919
    2020 - C++ programozási nyelv ismerete