Szakdolgozat-, nagyprogram- és TDK-témák

Gráfok ábrázolása

Gráfok vizualizációja, azaz egy adott gráf pontjainak elhelyezése a síkon minél esztétikusabb, átláthatóbb formában.

Háttér

Gráfok (hálózatok) reprezentálása a síkban egy mind elméletileg, mind a gyakorlatban fontos és érdekes problémakör. A legalapvetőbb kerdés annak (algoritmikus) megválaszolása, hogy egy gráf síkgráf-e, azaz lerajzolható-e úgy a síkban, hogy az élei ne messék egymást. Ha a válasz igen, akkor természetes feladat megadni egy "minél tetszetősebb", minél áttekinthetőbb ilyen reprezentációt. Hasonlóan, feladat lehet nem síkbarajzolható gráfok megjelenítése is. Ezek a problémák tovább ágaztathatók aszerint, hogy az éleket egyenessel, egyszeresen tört vonallal, esetleg tetszöleges görbével kívánjuk reprezentálni, esetleg aszerint, hogy a reprezentálandó gráf rendelkezik-e valamilyen speciális tulajdonsággal.

E feledatkör fontos szerephez jut minden olyan döntéstámogató rendszerben, ahol valamilyen gráffal reprezentálható struktúrát (pl. egy kommunikációs hálózatot, UML diagrammot, egymással összefüggö entitások kapcsolati hálóját stb.) kell a felhasználó számára áttekinthető módon megjeleníteni. A terület gyakorlati fontosságnak megfelelően az elmúlt évtizedekben gráf-ábrázoló algoritmusok sokaságát fejlesztették ki.

Feladat

A jelentkezők feladata az irodalomban fellelhető gráf reprezentáló algoritmusok áttekintése, a gyakorlatban alkalmazható algoritmusok közül néhány implementálása, összehasonlítása esetleg továbbfejlesztése. Cél, hogy a minél több alfeladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba.

A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Előfeltételek

• C++ programozási nyelv ismerete
• alap gráfelméleti ismeretek
• angol nyelvismeret

Többtermékes folyam-algoritmusok

Többtermékes folyam-algoritmusok implementálása és összehasonlítása.

Háttér

A többtermékes folyamok a hagyományos folyam-feladatok általánosításai több forrás-cél pár esetére. A különböző forrás-cél párok közötti forgalmak ("termékek") együttesen használják az éleken levő kapacitásokat.

E feledatkör fontos szerephez jut például különféle hálózattervezési (telekommunikációs, közlekedési), útvonalválasztási és áramkörtervezési feladatok megoldásakor.

Elméleti szempontból ez a problémaosztály könnyen kezelhető - azaz létezik polinomiális futásidejű algoritmus - azonban alkalmazásokban gyakran felmerülnek olyan méretű feladatok, amiket ezek az algoritmusok már nem képesek elfogadható időn belül megoldani. Ezért az egzakt megoldó algorimusok mellett hatékony közelítő eljárásokat és heurisztikus módszereket is kifejlesztettek.

Feladat

A jelentkezők feladata az irodalomban fellelhető többtermékes folyam-algoritmusok áttekintése, a gyakorlatban alkalmazhatók közül néhány implementálása, összehasonlítása esetleg továbbfejlesztése. Cél, hogy a minél több alfeladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba.

A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Előfeltételek

• C++ programozási nyelv ismerete
• alap gráfelméleti ismeretek
• angol nyelvismeret

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 szakdolgozat, nagyprogram é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