| 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++.
|
|---|