20.500.12556/RUL-170849 Gasilec delo diplomskega seminarja Firefighter 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. This thesis studies the Firefighter game on graphs in which a firefighter protects one vertex per round while fire spreads through unprotected vertices. We analyze two strategies, the optimal and the greedy, and assess their effectiveness across various graph families. We introduce the concepts of save number and surviving rate to measure strategy success. The surviving rate is computed explicitly for basic graph classes such as paths, cycles, complete graphs, wheels, and bipartitive graphs. We also establish lower bounds for the surviving rate on trees and show that among all connected graphs, trees attain the highest possible surviving rate. Finally, we demonstrate that the greedy strategy provides an efficient approximation of the optimal strategy on trees. Gasilec rešitveno število stopnja preživetja Firefighter save number surviving rate true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-07-18 08:15:04 2025-07-18 08:15:08 2025-07-20 03:46:36 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 150758 242994179 18157.pdf 18157.pdf 1 4B124CE4F5FC92AC173272176ADEDAB0 055abcbf93fa17149c957938381e3605724e1e2493860e996ef0586a1edc2e5b 8e1f53ed-639e-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=213109 Fakulteta za matematiko in fiziko 0 0 0