COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
06/17/09 11:35:30 (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

    v3 v4  
    11= Irányítatlan gráfok k-élösszefüggővé irányítása =
    22
    3 Különböző irányítási algoritmusok futásidejének vizsgálata.
     3Különböző irányítási algoritmusok implementálása és összehasonlítása.
    44
    55== Háttér ==
    66
    7 Nash-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.
     7Nash-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 néhány az eredetinél általánosabb feladatokra is alkalmazható. Érdekes kérdés, hogy a gyakorlatban melyik megközelítés mennyire hatékony.
    88
    99== Feladat ==