Ničelna prisila : magistrsko delo

Meršak, Ines (avtor), Klavžar, Sandi (mentor)

Množ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.

• Jezik: Slovenski jezik
• Ključne besede: ničelna prisila, produkt grafov, računska zahtevnost
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2019
• PID: 20.500.12556/RUL-111294
• UDK: 519.17
• COBISS.SI-ID: 18732121
• Datum objave v RUL: 27.09.2019

MERŠAK, Ines, 2019, Ničelna prisila : magistrsko delo [na spletu]. Magistrsko delo. [Dostopano 19 april 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=111294

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Zero forcing

Izvleček

Zero forcing set of graph $G$ is a subset $Z$ of vertices for which the following holds: if initially the vertices from $Z$ are coloured black and we apply the colour change rule repeatedly, then at the end of the process all vertices of $G$ should be black. Here the colour change rule is defined as: a black vertex $u$ forces the change of colour in a white negihbour $v$, if $v$ is the only white neighbour of $u$. The zero forcing number of a graph is the size of the smallest zero forcing set. In this work, we list and prove results for some well known families of graphs, lower and upper bounds of the zero forcing number and characterise the graphs for which these bounds are tight. Some upper bounds for various products of graphs and connections to other graph parameters, such as domination and independence number, are also given. We implement algorithms for checking whether a set is zero forcing and for calculating the zero forcing number of a general graph in C++. The latter algorithms are exponential, however due to NP-hardness of the problem, polynomial time complexity (most likely) cannot be obtained. Some additional complexity results for closely related problems are also listed.

• Ključne besede: zero forcing, graph product, computational complexity