magistrsko delo
Ines Meršak (Avtor), Sandi Klavžar (Mentor)

Povzetek

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.

Ključne besede

ničelna prisila;produkt grafov;računska zahtevnost;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: [I. Meršak]
UDK: 519.17
COBISS: 18732121 Povezava se bo odprla v novem oknu
Št. ogledov: 1662
Št. prenosov: 213
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Zero forcing
Sekundarni povzetek: 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.
Sekundarne ključne besede: zero forcing;graph product;computational complexity;
Vrsta dela (COBISS): Magistrsko delo/naloga
Študijski program: 0
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 2. stopnja
Strani: IX, 56 str.
ID: 11234418