COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Temak


Ignore:
Timestamp:
03/17/09 08:41:08 (10 years ago)
Author:
Alpar Juttner
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Temak

    v1 v1  
     1= Nagyprogram, TDK és diplomamunka témák =
     2
     3= Gráfok ábrázolása =
     4
     5Gráfok vizualizációja, azaz egy adott gráf pontjainak elhelyezése a síkon minél esztétikusabb, átláthatóbb formában.
     6
     7== Háttér ==
     8
     9Grá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.
     10
     11E 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.
     12
     13== Feladat ==
     14
     15A 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.
     16A feladat típusa
     17
     18A feledatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat, több jelentkező számára is.
     19
     20== Előfeltételek ==
     21
     22 - C++ programozási nyelv ismerete
     23 - alap gráfelméleti ismeretek
     24 - angol nyelvismeret
     25
     26= Többtermékes folyam-algoritmusok =
     27
     28Többtermékes folyam-algoritmusok implementálása és összehasonlítása.
     29
     30== Háttér ==
     31
     32A 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.
     33
     34E 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.
     35
     36Elmé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.
     37
     38== Feladat ==
     39
     40A 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.
     41A feladat típusa
     42
     43A feledatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat, akár több jelentkező számára is.
     44Előfeltételek
     45
     46 - C++ programozási nyelv ismerete
     47 - alap gráfelméleti ismeretek
     48 - angol nyelvismeret
     49
     50= Fák pakolása, fedés fákkal =
     51
     52Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés)
     53
     54== Háttér ==
     55
     56A ''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.
     57
     58A ''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.
     59Feladat
     60
     61== Feladat ==
     62
     63A 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.
     64
     65A feladatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat, akár több jelentkező számára is. Az is elképzelhető, hogy a két feladatkör közül csak az egyiket dolgozza fel a jelentkező.
     66
     67== Előfeltételek ==
     68
     69 - C++ programozási nyelv ismerete
     70 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     71 - angol nyelvismeret