Meno:Filip
Priezvisko:Husár
Názov:Cestová a stromová šírka kubických grafov
Vedúci:doc. RNDr. Robert Lukoťka, PhD.
Rok:2019
Kľúčové slová:grafy, cestová dekompozícia, cestová šírka, približná bisekcia grafu
Abstrakt:Cestová a stromová dekompozícia je rozčlenenie vrcholov grafu do množín vriec pričom platí, že každá hrana sa nachádza v niektorom vreci a každý vrchol je v súvislom úseku vriec. Napokon, vrecia tvoria cestu, prípadne strom, podľa dekompozície ktorá je vykonaná. Budeme sa zaoberať algoritmom cestovej dekompozície kubických grafov, ktorý bol publikovaný v článku F.V.Fomina a K.Hoieho. K jeho realizácii použijeme niekoľko algoritmov bisekcie kubického grafu z článku B.Moniena a R.Preisa. Vďaka dekompozíciám s malou šírkou rozkladu vieme riešiť mnoho NP-ťažkých problémov na grafoch efektívne. V tejto práci implementujeme spomínané algoritmy na výpočet približnej bisekcie a cestovej dekompozície, ktorej šírka rozkladu bude vo väčšine prípadov približne (1/6)|V(G)|. Implementácia bude z dôvodu jej rýchlosti oproti článkom odlišná v niektorých detailoch. Použijeme pritom knižnicu ba-graph v jazyku C++.

Súbory bakalárskej práce:

Bakalárka.pdf
husar22_bachelor.zip