| | 1 | == Algoritmusok összehasonlítása irányítatlan gráfok k-élösszefüggővé irányítására == |
| | 2 | |
| | 3 | Különböző irányítási algoritmusok futásidejének vizsgálata. |
| | 4 | |
| | 5 | === Háttér === |
| | 6 | 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. |
| | 7 | |
| | 8 | === Feladat === |
| | 9 | A 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 | |
| | 11 | A 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 |
