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