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.
|
