| | 1 | == Fák pakolása, fedés fákkal == |
| | 2 | |
| | 3 | Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés) |
| | 4 | |
| | 5 | === Háttér === |
| | 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 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 | |
| | 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 | |
| | 11 | === Feladat === |
| | 12 | |
| | 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. |
| | 14 | |
| | 15 | A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is. |
| | 16 | Az is elképzelhető, hogy a két feladat közül csak az egyiket dolgozza fel a jelentkező. |
| | 17 | |
| | 18 | === Előfeltételek === |
| | 19 | |
| | 20 | - C++ programozási nyelv ismerete |
| | 21 | - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok |
| | 22 | - angol nyelvismeret |
