COIN-OR::LEMON - Graph Library

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


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

--

Legend:

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

    v2 v3  
    1 == Algoritmusok összehasonlítása irányítatlan gráfok k-élösszefüggővé irányítására ==
     1= Irányítatlan gráfok k-élösszefüggővé irányítása =
    22
    33Különböző irányítási algoritmusok futásidejének vizsgálata.
    44
    5 === Háttér ===
     5== Háttér ==
     6
    67Nash-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.
    78
    8 === Feladat ===
     9== Feladat ==
     10
    911A 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.
    1012
    1113A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
    1214
    13 === Előfeltételek ===
     15== Előfeltételek ==
    1416
    1517 - C++ programozási nyelv ismerete