Rocníkový projekt

Názov projektu: Algoritmus na urcenie cyklickej súvislosti grafov


Meno študenta: Fedir Matsiutsia

E-mail študenta: matsiutsia2@uniba.sk


Meno školitela: Ján Mazák

E-mail školitela: jan.mazak@fmph.uniba.sk


Report za zimný semester

Report za letný semester

GitHub


Opis a ciel: Spravit nanovo a urobit 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).