| Abstrakt: | Práca sa venuje algoritmickému overovaniu hypotézy o nerepetitívnom zoznamovom
farbení ciest, ktoré hovorí, že pre každú cestu a každé priradenie množiny farieb veľ-
kosti 3 vrcholom cesty je vždy možné nájsť nerepetitívne farbenie, pričom farba kaž-
dého vrchola je vybraná z jemu priradenej množiny farieb. Nerepetitívne farbenie je
také vrcholové farbenie grafu, kde pre každú cestu párnej dĺžky platí, že postupnosť
farieb ľavej polovice cesty nie je rovnaká ako postupnosť farieb pravej polovice cesty.
V práci sme navrhli efektívnu implementáciu založenú na maticovej reprezentácii ciest,
množine redukčných pravidiel, cache mechanizme a využití lineárneho programovania.
Kombináciou týchto techník sme výrazne znížili počet ciest, ktoré bolo potrebné analy-
zovať. Overenie pomocou tejto implementácie potvrdilo platnosť hypotézy pre všetky
cesty s dĺžkou do 13 vrátane.
|
|---|