Dr. techn. Ing. Jan Legerský

Dr. techn. Ing. Jan Legerský

Mgr. Michal Opler, Ph.D.

Katedra teoretické informatiky

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.

Dr. techn. Ing. Jan Legerský

Dr. rer. nat. Rodrigo Augusto da Silva Alves

Katedra aplikované matematiky

Tato práce se zaměřuje na aplikaci zpětnovazebného učení v teorii strukturální tuhosti. Cílem této práce je znovu implementovat evoluční algoritmus hlubokého zpětnovazebného učení, deep cross-entropy method, a aplikovat ji v teorii strukturální tuhosti. V roce 2021 Adam Zsolt Wagner využil tento algoritmus k vyvrácení některých hypotéz pomocí nalezení protipříkladů. Tento algoritmus maximalizuje určitou hodnotící funkci a hlavním cílem této práce je najít minimálně tuhý graf s vysokým počtem realizací v rovině. Teorie strukturální tuhosti je odvětvím matematiky, které studuje grafy a vlastnost tuhosti. Realizace grafu je zobrazení vrcholů do roviny. Dvojice realizace a grafu je považována za tuhou, pokud ji nelze spojitě deformovat se zachováním délek hran. Rigidita je vlastnost grafu při použití generické realizace. Existující implementace počítající počet realizací pro daný minimálně tuhý graf je využita v této práci. Počty realizací byly již dříve spočítány pro všechny minimálně tuhé grafy s maximálně 14 vrcholy. Pro větší grafy existují pouze dolní odhady maximálního počtu. Všechny nejlepší známé grafy s až 15 vrcholy byly v této práci nalezeny v podstatně kratším čase. Výsledkem této práce je několik efektivních reimplementací deep cross-entropy method ve formě Python skriptů. Dvě reimplementace byly vytvořeny pro reprodukci Wagnerových výsledků a jsou obecné, takže je lze použít i pro jiné problémy. Bylo ukázáno, že jsou přibližně 50krát rychlejší než původní implementace vytvořená Wagnerem. Další dvě implementace byly vytvořeny na konstrukci minimálně tuhých grafů s vysokým počtem realizací. Všechny implementace jsou paralelizované a snadno spustitelné na serveru s vysokým počtem CPU jader, což umožňuje využít veškeré dostupné výpočetní proštředky.