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