| Meno: | Karolína
|
|---|
| Priezvisko: | Pisoňová
|
|---|
| Názov: | Špeciálne nikde nulové toky na grafoch
|
|---|
| Vedúci: | doc. RNDr. Edita Máčajová, PhD.
|
|---|
| Rok: | 2025
|
|---|
| Kľúčové slová: | Nikde nulové toky, 5-toková hypotéza, toková sila, nepotlačiteľné hrany, kubické grafy, snarky
|
|---|
| Abstrakt: | Nikde nulové toky sú významnou oblasťou v teórii grafov, ktorá je skúmaná už od polovice dvadsiateho storočia. V tejto diplomovej práci sa zaoberáme špeciálnymi druhmi nikde nulových tokov a ich vlastnosťami. Na začiatok uvádzame dôležité definície, ktoré neskôr využívame v práci. Uvádzame tiež známe poznatky o nikde nulových tokoch a ich vzťahoch k iným významným problémom v teórii grafov. Ďalej popisujeme navrhnuté a implementované algoritmy na hľadanie špeciálnych nikde nulových tokov vrátane ich prevodu na SAT problém. Vyslovujeme hypotézy o vzťahu počtov nikde nulových k-tokov a nikde nulových Zk-tokov, tvrdenia týkajúce sa nami definovaných jedinečných nikde nulových k-tokov s dôkazmi pre niektoré nekonečné triedy grafov a vyslovujeme tvrdenie o vzťahu medzi hodnotou tokovej sily grafu a existenciou nepotlačiteľných hrán v danom grafe.
|
|---|