Meno:Tatiana
Priezvisko:Husárová
Názov:Banova-Linialova hypotéza
Vedúci:doc. RNDr. Edita Máčajová, PhD.
Rok:2023
Kľúčové slová:Banova-Linialova hypotéza, 2-bisekcia, extremálne grafy, maximalizácia rozdielu
Abstrakt:V našej práci sme sa venovali rôznym variáciám a možným zosilneniam Banovej-Linialovej hypotézy, ktorá hovorí o existencii 2-bisekcie pre každý kubický bezmostový graf okrem Petersonovho. V prvej časti sme sa zameriavali na extremálne grafy pre Banovu-Linialovu hypotézu, kde sme skúmali množinu grafov s najmenším počtom 2-bisekcií a množinu grafov s najväčším počtom 2-bisekcií. Popísali sme množinu grafov s minimálnym počtom 2-bisekcií a pre každý graf z tejto množiny sme dokázali existenciu jedinej 2-bisekcie. Pre množinu s maximálnym počtom 2-bisekcií sme popísali správanie grafov s rastúcim počtom vrcholov. V druhej časti sme upustili od podmienky rovnakého počtu vrcholov v oboch partíciách 2-bisekcie a pozorovali sme maximálny rozdiel vrcholov v týchto partíciách. Zadefinovali sme konštrukciu, ktorou sme dokázali zostrojiť graf s ľubovoľne veľkým rozdielom vrcholov medzi dvoma partíciami 2-bisekcie a teoreticky sme odvodili, že tento rozdiel je najväčší možný vzhľadom na počet vrcholov grafu.

Súbory bakalárskej práce:

husarova.pdf
zdrojovy_kod.zip

Súbory prezentácie na obhajobe:

obhajoby.pdf

Upraviť