Razpon grafa

magistrsko delo

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[L. Drožđek]
UDK:	519.17(043.2)
COBISS:	127295235
Št. ogledov:	5
Št. prenosov:	1
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Span of a graph
Sekundarni povzetek:	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.
Sekundarne ključne besede:	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;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	niv. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	VIII, 45 f.
ID:	15958813