| Meno: | Rudolf
|
|---|
| Priezvisko: | Starovský
|
|---|
| Názov: | Najkratšie pokrytie grafu cyklami
|
|---|
| Vedúci: | RNDr. Edita Máčajová, PhD.
|
|---|
| Rok: | 2010
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | najkratšie pokrytie cyklami, cykly, kružnice, snarky, pokrytie 1-faktormi, dvojité pokrytie cyklami, prechádzka čínskeho poštára
|
|---|
| Abstrakt: | V tejto diplomovej práci sa venujeme téme Najkratších pokrytí cyklami.
Zvlášť sme sa zamerali na kubické grafy a skúmanie niektorých známych nekonečných tried snarkov, ktoré dosahujú dolné hranice pre celkovú dĺžku ako
aj počet cyklov pokrytia. Všímame si súvislosť s problémom pokrytia grafu
štyrmi 1-faktormi. Podobne sa zaoberáme aj prepojením s problémom dvojitého pokrytia cyklami a prechádzky čínskeho poštára. Na základe overenia
vlastností pre snarky na malom počte vrcholov vyslovujeme niekoľko hypotéz, ktoré sa týkajú tohto prepojenia.
Ako prílohu prikladáme program na nájdenie najkratšieho pokrytia cyklami kubického grafu a niektoré programy, ktoré sme používali počas overovania spomínaných vlastností.
|
|---|