Ročníkový projekt

Názov projektu: Algoritmus na určenie cyklickej súvislosti grafov

Meno študenta: Fedir Matsiutsia

E-mail študenta: matsiutsia2@uniba.sk

Meno školiteľa: Jan Mazak

E-mail školiteľa: jan.mazak@fmph.uniba.sk

Opis a cieľ: Spraviť nanovo a urobiť lepší algoritmus z bakalárskej práce Drahomíra Mrózeka, presnejšie:

1. Urcenie cyklickej suvislosti kubickeho grafu (existujuci algoritmus vyuzivajuci toky)
2. Urcenie cyklickej suvislosti 4-regularneho grafu, pripadne d-regularneho pre d cca do 10, a zistenie ich rychlosti na praktickych vstupoch
3. Vyhladanie casti grafu urcenych malymi rezmi, aj s dorazom na hladanie rezu, ktory deli graf na priblizne rovnake casti (ak taky existuje)
4. Trivialneho hladania rezu odoberanim k-tice hran, pre ucely testovania a porovnania rychlosti

Implementacia zahrna rozsiahle testy na uplnych zoznamoch malych grafov aj nahodne generovanych velkych grafoch. Implementacia musi mat modularnu strukturu, aby bolo mozno testovat a pripadne vymenit jednotlive funkcie a casti (napr. hladanie toku pomocou kniznice boost + porovnanie rychlosti).