Razpon grafa

magistrsko delo

Lara Drožđek (Author), Andrej Taranenko (Mentor)

Abstract

V magistrskem delu predstavimo osnove teorije grafov, razpone grafa, z njimi povezane pojme in rezultate. Pojem razpona grafa povežemo z določanjem največje varnostne razdalje, ki jo lahko v grafu ohranjata dva igralca, ki želita obiskati vsa vozlišča (ali vse povezave) grafa. Predstavimo tudi tri pravila premikanja, ki jih morata igralca med premikanjem po grafu upoštevati, in jih povežemo s produkti grafov. V delu je podana tudi karakterizacija grafov, v katerih ni mogoče ohranjati pozitivne varnostne razdalje med igralcema glede na podano pravilo premikanja po grafu. Na koncu predstavimo polinomski algoritem za določanje razpona grafa. Katero različico razpona grafa algoritem izračuna, je odvisno od podanega pravila premikanja po grafu.

Keywords

magistrska dela;krepki razpon grafa;direktni razpon grafa;kartezični razpon grafa;produkti grafov;karakterizacija;algoritem;varnostna razdalja;

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[L. Drožđek]
UDC:	519.17(043.2)
COBISS:	127295235
Views:	5
Downloads:	1
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Span of a graph
Secondary abstract:	In the thesis, we define the basics terminology of graph theory and spans of a graph and present theorems related to them. We connect spans of a graph with determining the maximum safety distance two players can keep at all times while traversing all vertices or all edges of a graph. We also introduce three movement rules, which players must consider while traversing a graph, and provide a relation between those rules and graph products. In the thesis, we also characterize the graphs in which it is impossible to keep a positive safety distance between the two players at all times, according to the movement rule. At the end, we introduce a polynomial time algorithm to compute the chosen span for a given graph.
Secondary keywords:	master theses;strong span of a graph;direct span of a graph;Cartesian span of a graph;graph products;characterisation;algorithm;safety distance;Teorija grafov;Grafične metode;Algoritmi;Univerzitetna in visokošolska dela;
Type (COBISS):	Master's thesis/paper
Thesis comment:	niv. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	VIII, 45 f.
ID:	15958813