| Abstrakt: | Táto práca sa zameriava na zostavenie zoznamu minimálnych nezafarbiteľných podgrafov snarkov a analýzu ich vlastností. Snarky sa stávajú čoraz populárnejšími, pretože majú potenciál poskytnúť protipríklady k niekoľkým hypotézam v teórii grafov. Aby sme vyriešili absenciu zoznamu minimálnych nezafarbiteľných podgrafov, vygenerovali sme tieto podgrafy algoritmom, ktorý postupne odstraňuje hrany a overuje minimalitu a nezafarbiteľnosť výsledných podgrafov. Minimálne grafy sú tie s najmenším počtom prvkov, pričom sú stále nezafarbiteľné. Konkrétne, 3-hranovo-nezafarbiteľné. Na optimalizáciu času výpočtu sme použili memoizáciu. Ako vstupy sme stiahli rôzne sady grafov z online databázy. Naše výsledky zahŕňajú údaje o vygenerovaných podgrafoch, ako je ich rozdelenie podľa počtu vrcholov alebo časov trvania jednotlivých generovaní, atď. Zistenia sú prezentované v mnohých tabuľkách a obrázkoch.
|
|---|