COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Irányítatlan gráfok k-élösszefüggővé irányítása


Ignore:
Timestamp:
04/14/09 17:56:40 (10 years ago)
Author:
Erika Kovács
Comment:

--

Legend:

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

    v1 v1  
     1== Algoritmusok összehasonlítása irányítatlan gráfok k-élösszefüggővé irányítására ==
     2
     3Különböző irányítási algoritmusok futásidejének vizsgálata.
     4
     5=== Háttér ===
     6Nash-Williams tétele szerint egy irányítatlan gráfnak pontosan akkor létezik k-élösszefüggő irányítása, ha a gráf 2k-élösszefüggő. Egy jó irányítás megtalálására több algoritmus is született, melyekből több az eredeti tételnél általánosabb feladatokra is alkalmazható. Érdekes kérdés, hogy a gyakorlatban melyik megközelítés bizonyul jobbnak.
     7
     8=== Feladat ===
     9A feladat ezen algoritmusok közül minél több hatékony implementálása, esetleg speciális gráfosztályokon gyorsabbak fejlesztése, a futásidők összevetése. A téma szoros kapcsolatban áll a leemelések elméletével.
     10
     11A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     12
     13=== Előfeltételek ===
     14
     15 - C++ programozási nyelv ismerete
     16 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     17 - angol nyelvismeret