COIN-OR::LEMON - Graph Library

Changes between Version 2 and Version 3 of Gráfok ábrázolása


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

--

Legend:

Unmodified
Added
Removed
Modified
  • Gráfok ábrázolása

    v2 v3  
    1 == Gráfok ábrázolása ==
     1= Gráfok ábrázolása =
    22
    33Gráfok vizualizációja, azaz egy adott gráf pontjainak elhelyezése a síkon minél esztétikusabb, átláthatóbb formában.
    44
    5 === Háttér ===
     5== Háttér ==
    66
    77Grá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.
     
    99E 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.
    1010
    11 === Feladat ===
     11== Feladat ==
    1212
    1313A 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.
     
    1515A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
    1616
    17 === Előfeltételek ===
     17== Előfeltételek ==
    1818
    1919 - C++ programozási nyelv ismerete