| Meno: | Juraj
|
|---|
| Priezvisko: | Žitňanský
|
|---|
| Názov: | Generovanie kubických grafov zo 7-regulárnych grafov
|
|---|
| Vedúci: | doc. RNDr. Robert Lukoťka, PhD.
|
|---|
| Rok: | 2021
|
|---|
| Kľúčové slová: | kubický graf, snark, zafarbiteľnosť, izomorfizmus, automorfizmus, nikde-nulový tok
|
|---|
| Abstrakt: | Hlavným cieľom diplomovej práce bol návrh a implementácia algoritmov, alebo programov určených na vygenerovanie neizomorfných kubických grafov s cyklickou súvislosťou 7 a následné overenie zafarbiteľnosti daných grafov, čiže zisťovanie či daný graf je snark alebo nie. V práci uvádzame spôsoby ako obmedziť nutnosť overovania izomorfizmu za pomoci globálneho zoznamu neizomorfných grafov. Podarilo sa nám vytvoriť viacero programov, ktoré sú schopné generovať hľadané grafy a taktiež program na zisťovanie zafarbiteľnosti, respektíve existencie nikde-nulového Z2xZ2 toku. Všetky tieto
programy využívajú knižnice ba-graph a nauty.
|
|---|