Szakdolgozat- és TDK-témák

Az alábbi témák a LEMON programkönyvtár fejlesztéséhez, illetve alkalmazásához kapcsolódnak. Ezek elsősorban példaként szolgálnak, nem konkrét javaslatként. Az érdeklődőknek személyre szabott feladatokat, témákat tudunk összeállítani BSc/MSc szakdolgozathoz és TDK-hoz egyaránt.

• Irányítatlan gráfok k-élösszefüggővé irányítása

Különböző irányítási algoritmusok implementálása és összehasonlítása.

• Irányított gráf erősen összefüggővé tétele

Egy algoritmus implementálása, amely egy irányított gráfot minimális számú él összehúzásával erősen összefüggővé tesz.

• 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).

• Steiner-fa keresése

Hatékony közelítő és heurisztikus algoritmusok implementálása és összehasonlítása a Steiner-fa feladatra.

• Steiner-hálózat keresése

Lineáris programozást használó 2-approximációs algoritmus implementálása irányítatlan gráfban Steiner-hálózat keresésére.

• Párhuzamos gráfalgoritmusok

Különböző gráfelméleti, hálózattervezési feladatokra párhuzamos (többszálú) algoritmusok implementálása és összehasonlítása.

• Bináris formátum gráfok tárolására

Egy általános bináris fájlformátum kidolgozása gráfok tárolásához és kezelőfüggvények implementálása.

• Gráfok direkt szorzata

Gráfok direkt szorzatát megvalósító dinamikus adatstruktúra implementálása.

• Élgráf adatstruktúra

Egy irányítatlan gráf élgráfját megvalósító dinamikus adatstruktúra implementálása.

• 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.

• Metaheurisztikák implementálása

Különböző metaheurisztikák implementálása, tesztelése és összehasonlítása.

• Utazóügynök feladat

Approximációs, heurisztikus és exponenciális algoritmusok implementálása és összehasonlítása az utazóügynök problémára.

• Többtermékes folyam-algoritmusok

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

• Forgalmi mátrix becslése IP hálózatokban

A rendelkezésre álló adatforgalmi adatok alapján a forgalmi mátrix becslése IP hálózatokban.

• pyLemon modul fejlesztése

A LEMON használatának lehetővé tétele a Python programozási nyelvből

• Véletlen gráfok generálása

Adott gráfosztályból egy véletlen elem generálása egyenletes vagy más eloszlás szerint.

• Gráfosztályok előállítása konstruktív karakterizáció segítségével

Algoritmus kifejlesztése bizonyos gráfosztályokba tartozó összes n csúcsú gráf felsorolására (generálására).

• Gráfelméleti sejtés-ellenőrző modul fejlesztése

Egy olyan általános keretrendszer kidolgozása, amely kisméretű példák ellenőrzésével segíti a gráfelméleti kutatók munkáját.