<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:dc="http://purl.org/dc/elements/1.1/"><rdf:Description rdf:about="https://dk.um.si/IzpisGradiva.php?id=82149"><dc:title>Razpon grafa</dc:title><dc:creator>Drožđek,	Lara	(Avtor)
	</dc:creator><dc:creator>Taranenko,	Andrej	(Mentor)
	</dc:creator><dc:subject>krepki razpon grafa</dc:subject><dc:subject>direktni razpon grafa</dc:subject><dc:subject>kartezični razpon grafa</dc:subject><dc:subject>produkti grafov</dc:subject><dc:subject>karakterizacija</dc:subject><dc:subject>algoritem</dc:subject><dc:subject>varnostna razdalja</dc:subject><dc:description>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 nam algoritem izračuna, je odvisno od podanega pravila premikanja po grafu.</dc:description><dc:publisher>[L. Drožđek]</dc:publisher><dc:date>2022</dc:date><dc:date>2022-07-21 10:20:05</dc:date><dc:type>Magistrsko delo/naloga</dc:type><dc:identifier>82149</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>