Consider a model of fire spreading through a graph; initially some vertices are burning, and at every given time-step fire spreads from burning vertices to their neighbours. The firefighter problem is a solitaire game in which a player is allowed, at every time-step, to protect some non-burning vertices (by effectively deleting them) in order to contain the fire growth. How many vertices per turn, on average, must be protected in order to stop the fire from spreading infinitely? Here we consider the problem on $\mathbb{Z}^2\times [h]$ for both nearest neighbour adjacency and strong adjacency. We determine the critical protection rates for these graphs to be $1.5h$ and $3h$, respectively. This establishes the fact that using an optimal two-dimensional strategy for all layers in parallel is asymptotically optimal.
翻译:考虑一个通过图表传播火的模型; 最初有些顶端正在燃烧, 并且在每个特定时间段从燃烧的脊椎向邻居扩散火力。 消防员的问题是一个单调游戏, 允许玩家在每一个时间段保护一些非燃烧的脊椎( 有效删除它们), 以遏制火灾的蔓延。 平均来说, 每转圈要保护多少个顶端, 才能阻止火灾无穷无尽的蔓延 。 我们在这里认为, $\ mathbb ⁇ 2\\ times 上的问题对于近邻的相邻关系和强相邻关系来说都是 $h] 。 我们确定这些图形的关键保护率分别为 1.5 h 美元 和 3 h 美元 。 这证明了一个事实, 对所有平行层使用最佳的二维策略是同样最佳的 。