Abstrakt: | Snarky sú netriviálne kubické grafy, ktoré nie sú hranovo 3-zafarbiteľné. Táto práca nadväzuje na výskum novoobjavenej metódy konštrukcie snarkov – dvojitej superpozície. V práci hľadáme grafy s párnou kružnicou s istou vlastnosťou, na základe ktorej vieme povedať, že po aplikovaní dvojitej superpozície správnym spôsobom na daný graf vznikne snark. Overíme prítomnosť žiadanej kružnice v známych nekonečných triedach snarkov, Blanušových a Isaacsovych. Zároveň na základe výsledkov programu overujúceho prítomnosť danej kružnice v grafe vyslovíme hypotézu, že kružnica s danou vlastnosťou je prítomná v každom snarku. Dokážeme, že najmenší protipríklad pre hypotézu nemôže obsahovať malé rezy, ani malé cykly. Zároveň pravdivosť hypotézy podporíme výsledkami programu spustenom na všetkých netriviálnych snarkoch do 36 vrcholov (vrátane).
|
---|