Ničelna prisilaMeršak, Ines (Avtor) Klavžar, Sandi (Mentor) ničelna prisilaprodukt grafovračunska zahtevnostMnožica ničelne prisile grafa $G$ je taka podmnožica vozlišč $Z$, za katero velja: če na začetku pobarvamo vozlišča iz $Z$, nato pa uporabljamo pravilo za širjenje barve, dokler se dogajajo spremembe, morajo biti na koncu pobarvana vsa vozlišča grafa $G$. Pri tem je pravilo širjenja barve tako, da pobarvano vozlišče $u$ spremeni barvo soseda $v$ natanko tedaj, ko je ta edini še nepobarvan sosed vozlišča $u$. Število ničelne prisile grafa $G$ je velikost najmanjše take množice ničelne prisile. Delo obravnava ničelno prisilo nekaterih pogostih družin grafov, zgornje in spodnje meje zanjo in karakterizira grafe, ki te meje dosežejo. Obravnavane so tudi zgornje meje za nekatere produkte grafov in povezave ničelne prisile z nekaterimi drugimi grafovskimi parametri, kot sta npr. dominacijsko število in neodvisnostno število. V sklopu dela so v C++ implementirani algoritmi za preverjanje, ali je množica res množica ničelne prisile, in za izračun števila ničelne prisile za dani graf $G$. Slednji so eksponentni, vendar za splošen graf (najverjetneje) ne moremo doseči polinomske časovne zahtevnosti, saj je problem NP-težek. Predstavljeni so tudi nekateri drugi rezultati kompleksnosti za probleme, ki so tesno povezani z ničelno prisilo.20192019-09-27 07:45:32Magistrsko delo/naloga111294UDK: 519.17VisID: 102165COBISS_ID: 18732121sl