Abstrakt: | Skúmali sme pokrytie kubických grafov perfektnými páreniami - podmnožinami hrán, z ktorých žiadne dve nie sú navzájom incidentné a zároveň každý vrchol grafu je incidentný s presne jednou z týchto hrán. Cyklická súvislosť predstavuje najmenší počet hrán ktorý musíme z grafu odstrániť aby sme dostali oddelené cykli vo výsledných komponentoch. Pozerali sme sa na pokrytia s tromi perfektnými páreniami. Zaujímali nás grafy s cyklickou súvislosťou $3$ a viac. Za pomoci výpočtovej sily sme ukázali niektoré vlastnosti určitých multipólov a našli spôsob ako pre každé racionálne čislo z intervalu $\left(\frac{23}{27}, 1\right)$ nájsť graf s cyklickou súvislosťou $3$, čije najlepšie pokrytie tromi perfektnými páreniami je presne toto číslo. Podarilo sa nám dostať podobný výsledok aj pre cyklickú súvislosť $4$ a interval $\left(\frac{28}{31}, 1\right)$.
|
---|