| Abstrakt: | Mnohé známe hypotézy v teórii grafov je postačujúce dokázať pre kubické grafy, navyše pre hranovo 3-zafarbiteľné kubické grafy sú už tieto hypotézy dokázané.
V našej práci skúmame Kászonyiho funkciu, paralelnú a sériovú rezistenciu.
Tieto tri veličiny poskytujú isté charakteristiky pre tie kubické grafy, ktoré nie sú hranovo 3-zafarbiteľné.
Kászonyiho funkcia $\psi(e)$ vyjadruje počet rôznych hranových 3-farbení kubického grafu G po potlačení hrany e, pričom potlačenie hrany je odobratie hrany a vyhladenie incidentných vrcholov stupňa 2.
V práci určíme hodnotu Kászonyiho funkcie $\psi(e)$ pre ľubovoľnú hranu e každého grafu z dvoch nekonečných tried snarkov -- Isaacsových snarkov a zovšeobecnených Blanušových snarkov.
Paralelná rezistencia je minimálny počet po dvoch nezávislých hrán potrebný na to, aby po ich potlačení vznikol hranovo 3text-zafarbiteľný graf.
Sériová rezistencia je minimálny počet postupných potlačení hrán, ktorým z pôvodného grafu vznikne hranovo 3-zafarbiteľný graf. Teda u sériovej rezistencie povoľujeme aj potláčanie novovzniknutých hrán.
Ukážeme, že každý kubický graf má konečnú sériovú rezistenciu a ak má 1-faktor, tak má konečnú aj paralelnú rezistenciu.
Ďalej skonštruujeme nekonečnú triedu kubických grafov, ktoré majú nekonečnú paralelnú rezistenciu a nekonečnú triedu bezmostových kubických grafov, ktoré majú rozdielnu paralelnú a sériovú rezistenciu, pričom pre ľubovoľné prirodzené číslo n existuje v tejto triede taký graf G, pre ktorý je rozdiel jeho paralelnej a sériovej rezistencie väčší ako n. Súčasťou práce je aj program, ktorý v reálnom čase počíta hodnoty Kászonyiho funkcie, paralelnej a sériovej rezistencie pre kubické grafy do 80 vrcholov.
|
|---|