Meno:Peter
Priezvisko:Schmidt
Názov:Algoritmické vlastnosti vnorení grafov do plôch
Vedúci:Mgr. Michal Kotrbčík, PhD.
Rok:2015
Blok:INF
Kľúčové slová:vnorenie grafu, rod grafu, karteziánsky súčin, kompletný graf, Barnettova hypotéza, Tuttova hypotéza
Abstrakt:Táto práca sa venuje algoritmickým vlastnostiam vnorení grafov do plôch. Naším cieľom je určiť rod vybraných tried grafov. V prvej časti práce sa zameriavame na rody karteziánskych súčinov grafov s grafom $K_2$. S pomocou dosiahnutých teoretických výsledkov určíme rod súčinov kompletných grafov $K_n \Box K_2$ pre $n \leq 164$. Zvlášť dôležitý je výsledok pre $K_9$, ktorý ukazuje, že tento graf nedosahuje teoretický dolný odhad, ktorý uvádza Ringel. Druhá časť práce sa zameriava na konštrukciu protipríkladov k Tuttovej hypotéze. V práci určíme rod najmenšieho známeho protipríkladu. Zároveň sformulujeme postačujúce podmienky, za ktorých je možné známou konštrukciou zostrojiť triedu protipríkladov nižšieho rodu.

Súbory diplomovej práce:

CompleteEmbeddings.zip
dipl-schmidt.pdf