<?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://repozitorij.uni-lj.si/IzpisGradiva.php?id=170849"><dc:title>Gasilec</dc:title><dc:creator>Jankovič,	Nina	(Avtor)
	</dc:creator><dc:creator>Iršič Chenoweth,	Vesna	(Mentor)
	</dc:creator><dc:subject>Gasilec</dc:subject><dc:subject>rešitveno število</dc:subject><dc:subject>stopnja preživetja</dc:subject><dc:description>Delo diplomskega seminarja obravnava igro Gasilec na grafih, kjer gasilec v vsakem koraku zaščiti eno vozlišče, medtem ko se ogenj širi po nezaščitenih vozliščih. Analiziramo dve strategiji, optimalno in požrešno, ter njuno učinkovitost na različnih družinah grafov. Vpeljemo rešitveno število in stopnjo preživetja grafa kot meri uspešnosti strategij. Posebej podrobno obravnavamo stopnjo preživetja za osnovne razrede grafov, kot so poti, cikli, polni grafi, kolesa in dvodelni grafi. Dokazujemo spodnje meje za stopnjo preživetja dreves in pokažemo, da imajo ta med vsemi povezanimi grafi najvišjo možno stopnjo preživetja. Ugotovimo tudi, da požrešna strategija predstavlja učinkovito aproksimacijo optimalne strategije na drevesih.</dc:description><dc:date>2025</dc:date><dc:date>2025-07-18 08:15:04</dc:date><dc:type>Delo diplomskega seminarja/zaključno seminarsko delo/naloga</dc:type><dc:identifier>170849</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>