Bakalářské práce
Hledání NAC-obarvení: složitost a algoritmy
Autor
Petr Laštovička
Rok
2025
Typ
Bakalářská práce
Vedoucí
Dr. techn. Ing. Jan Legerský
Oponenti
Mgr. Michal Opler, Ph.D.
Katedra
Anotace
Jednou z otázek v strukturální teorii tuhosti (Rigidity Theory) je, zda realizace
vrcholů grafu do roviny je pohyblivá, tj. zda umožňuje spojitou deformaci
neměnící délku hran. Pohyblivá realizace souvislého grafu v rovině existuje
právě tehdy, když graf má NAC-obarvení, což je hranové obarvení dvěma
barvami takové, že pro každý cyklus jsou všechny hrany obarveny stejnou
barvou, nebo jsou každou barvou obarveny alespoň dvě hrany. Je NP-úplné
rozhodnout, zda graf má NAC-obarvení, v práci ukazujeme, že problém je
NP-úplný i pro grafy s maximálním stupněm pět. Představujeme značně
rychlejší algoritmus i s jeho implementací na hledání NAC-obarvení společně s různými heuristikami. Srovnáváme ho s předchozími algoritmy a porovnáváme
i heuristiky mezi sebou. Následně představujeme FPT algoritmus na počítání
NAC-obarvení parametrizovaný stromovou šířkou. Navíc popisujeme vztahy se
stabilními řezy grafu a implementujeme algoritmus pro jejich hledání v flexible
grafech.