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.
|
---|