Abstract: V tem magistrskem delu predstavimo različne dominacijske množice, in sicer popolno, učinkovito ter neodvisno. V prvem delu so navedeni osnovni pojmi v teoriji grafov, vse potrebne definicije, izreki in trditve. V nadaljevanju predstavimo nekaj znanih NP-polnih problemov s področja dominacije na grafih in jih podkrepimo s primeri za namen dokazovanja časovne zahtevnosti. Za izbrane dominacijske probleme prikažemo kompleksnost odločitvenih problemov z dominacijskimi lastnostmi za glavne dominacijske množice (popolna, učinkovita in neodvisna) in druge izbrane dominacije. Nazadnje posežemo še po problemih popolnega dominacijskega števila za neodvisno, povezano in celotno dominacijo.Keywords: dominacijska množica, popolna dominacijska množica, neodvisna dominacijska množica, učinkovita dominacijska množica, NP-polni problemi, dominacijsko številoPublished in DKUM: 07.10.2021; Views: 762; Downloads: 32 Full text (694,82 KB)
