| Meno: | Matúš |
|---|---|
| Priezvisko: | Nemčík |
| Názov: | Číslo cestového pokrytia kubických grafov |
| Vedúci: | doc. RNDr. Robert Lukoťka, PhD. |
| Rok: | 2026 |
| Kľúčové slová: | číslo cestového pokrytia, prehľadávanie s orezávaním, problém splniteľnosti, celočíselné lineárne programovanie |
| Abstrakt: | Táto bakalárska práca sa zaoberá číslom cestového pokrytia kubických grafov – minimálnym počtom vrcholovo disjunktných ciest potrebných na pokrytie všetkých vrcholov grafu. Skúmame teoretické vlastnosti tohto parametra a jeho vzťah k štruktúrnym vlastnostiam kubických grafov, najmä k stupňu súvislosti. Hlavným prínosom práce je implementácia a experimentálne porovnanie troch prístupov k výpočtu čísla cestového pokrytia: prehľadávanie s orezávaním, redukcia na problém splniteľnosti booleovských formúl a celočíselné lineárne programovanie. Experimenty na databáze kubických grafov rôznych veľkostí a stupňov súvislosti ukázali, že prístup s celočíselným lineárnym programovaním je vo väčšine prípadov najefektívnejší, zatiaľ čo redukcia na proglém splniteľnosti dosahuje lepšie výsledky pre grafy s číslom cestového pokrytia rovným jednej. Výsledky taktiež ukazujú, že výpočtová náročnosť jednotlivých prístupov závisí aj od hodnoty čísla cestového pokrytia a štruktúry grafu, nie len od počtu vrcholov. |
Súbory bakalárskej práce:
| nemcik-bc.pdf |
| nemcik26_bc.zip |
Súbory prezentácie na obhajobe: