Izbrane verzije dominacijskih množic in njihova časovna zahtevnostVišnar, Lučka (Avtor) Peterin, Iztok (Mentor) dominacijska množicapopolna dominacijska množicaneodvisna dominacijska množicaučinkovita dominacijska množicaNP-polni problemidominacijsko številoV 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.[L. Višnar]20212021-08-20 09:52:43Magistrsko delo/naloga79865UDK: 519.17:517.518.2(043.2)COBISS_ID: 78385923sl