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