.
Mgr. Jozef Rajník -- Výskum
Výskum
Farbenia a toky v kubických grafoch
Kubické grafy sú také grafy, v ktorých z každého vrcholu vychádzajú tri hrany. Tieto grafy majú veľký význam pri štúdiu slávnych desiatky rokov nedokázaných hypotéz v teórii grafov. Ide napr. o nasledovné hypotézy:
- Pre každý bezmostový graf existuje taká množina cyklov, že každá hrana sa nachádza práve v dvoch cyklov (Cycle double cover conjecture)
- Každý bezmostový graf má nikde nulový 5-tok (5-flow conjecture)
- V každom bezmostovom kubickom grafe možno nájsť 6 úplných párení takých, že každá hrana sa vyskytuje v práve dvoch z nich.
Pokiaľ hociktorá zo spomínaných hypotéz je pravdivá pre kubické grafy, tak je pravdivá aj pre všetky grafy. Taktiež sa medzi tieto hypotézy zaraďovala aj hypotéza, teraz už dokázaná veta, o 4 farbách.
Hranové farbenie grafu spočíva v tom, že každej hrane priradíme nejakú farbu tak, aby hrany vychádzajúce z rovnakého vrcholu mali navzájom rôzne farby. Ak chceme hranovo zafarbiť kubický graf, podľa Vizingovej vety nám na to stačia tri alebo štyri farby. Kubický graf s hranami zafarbený tromi farbami má veľmi peknú štruktúru a spomínané hypotézy možno v nich ľahko dokázať. Preto pri štúdiu týchto hypotéz sú dôležité kubické grafy, ktoré nejdú hranovo zafarbiť tromi farbami. Tieto grafy sa nazývajú snarky.
Snarky skúmam od svojho bakalárskeho štúdia a napísal som o nich nasledujúce práce:
- Decompositions of Small Snarks. Bakalárska práca, ktorá opisuje štruktúru všetkých snarkov s najviac 36 vrcholmi a vysvetľuje, prečo sa nedajú zafarbiť tromi farbami.
- Small critical snarksand their generalizations. Diplomová práca, ktorá sa zaoberá kritickými snarkami, t. j. snarkami, ktoré sú blízko k tomu, aby sa dali hranovo zafarbiť tromi farbami. V práci konštruujeme snarky zo zaujímavými vlastnosťami. Hlavne ide o striktne kritické snarky s cyklickou súvislosťou 6, ktoré doposiaľ neboli známe. Okrem toho sme pomocou počítača vygenerovali všetky snarky obvodu 6 a cyklickou súvislosťou 4 a 5, ktoré majú 40 vrcholov.
Didaktika informatiky
V rámci doplňujúceho pedagogického štúdia informatiky som vypracoval ako záverečnú prácu
Výučba časovej zložitosti programovna strednej škole. V práci som zozbieral niekoľko úloh, ktoré možno riešiť so študentami pripravujúcich sa na maturitu, pri ktorých sa objavuje priestor na diskusiu o rôznych spôsobov riešenia úloh a ich rôznej časovej efektivite.