| Meno: | Richard
|
|---|
| Priezvisko: | Bíró
|
|---|
| Názov: | Hamiltonovské kružnice v bipartitných kubických planárnych grafoch
|
|---|
| Vedúci: | RNDr. Ing. František Kardoš, PhD.
|
|---|
| Rok: | 2023
|
|---|
| Kľúčové slová: | Barnettova hypotéza, Hamiltonovská kružnica, kubický graf, planárny graf, bipartitný graf
|
|---|
| Abstrakt: | Barnettova hypotéza hovorí, že každý kubický planárny bipartitný 3-súvislý graf je Hamiltonovský. Existujú podgrafy (známe ako redukovateľné konfigurácie), ktoré sa nemôžu vyskytovať v najmenšom protipríklade. V našej práci sa zaoberáme skúmaním konfigurácií zložených zo stien malej veľkosti a ich klasifikáciou na redukovateľné a neredukovateľné vzhľadom na existenciu Hamiltonovskej kružnice. Súčasťou práce je aj implementácia algoritmov na generovanie a overovanie redukovateľných konfigurácií.
|
|---|