| Meno: | Nadiya |
|---|---|
| Priezvisko: | Balanchuk |
| Názov: | Jednoznačne hranovo-zafarbiteľné kubické grafy |
| Vedúci: | Mgr. Jozef Rajník, PhD. |
| Rok: | 2026 |
| Kľúčové slová: | kubický graf, hranové 3-farbenie, hamiltonovská kružnica, heteroc- hromatický 4-pól, Kempeho prepnutie |
| Abstrakt: | V práci skúmame jednoznačne hranovo 3-zafarbiteľné kubické grafy. V prvej časti upravujeme program Goedgebeura a spol. na generovanie grafov s práve k hamiltonovskými kružnicami tak, aby bol použiteľný pre algoritmické generovanie jednoznačne hranovo 3-zafarbiteľných kubických grafov. Najdôležitejšou úpravou je detekcia krátkych Kempeho cyklov, ktorá umožňuje skoršie ukončovanie vetiev vedúcich ku grafom s viac ako jedným farbením. Táto úprava overí vznik takého cyklu po pridaní hrany v konštantnom čase a v meraniach priniesla približne 40 % zrýchlenie. V druhej časti práce sa zaoberáme otvoreným problémom existencie heterochromatického 4-pólu majúceho práve jedno farbenie každého z typov (1, 2, 1, 2) a (1, 2, 2, 1). Samotné riešenie problému v práci neprezentujeme, uvádzame však niekoľko heterochromatických 4-pólov, ktoré považujeme za náročné prípady a vhodné na ďalšie skúmanie. Na záver konštruujeme nekonečnú triedu kubických grafov s práve dvoma hranovými 3-farbeniami, ktorá je zovšeobecnením jednej z tried z našej bakalárskej práce. Uvedená trieda má obvod 4 a cyklickú súvislosť 4 a oproti triedam z bakalárskej práce umožňuje väčšiu rôznosť grafov, ktoré do nej patria. |
Súbory diplomovej práce:
| main.pdf |
Súbory prezentácie na obhajobe: