摘要: 消防员问题 (Firefighter Problem) 是一个离散的动态传播模型，与疫情控制、谣言传播、森林防火等实际问题密切相关，它最早是由著名计算机理论学家 Hartnell 在 1995 年的第 25 届组合数学与计算大会上首次提出的。令 G = (V (G), E(G)) 是 n (n ≥ 2) 个顶点的连通图。假设火在图 G 中任意一个顶点 v 处燃起，消防员则选择未着火的顶点去保护(一旦某个顶点被保护，则在整个过程中都将处千被保护状态)，然后火蔓延到 v 的未加保护且没着火的邻点。依次下去，火和消防员交替地在图 G 上移动, 直到火不能继续蔓延，整个过程结束，消防员的任务是使最后获救的点数最多。令 sn(v) 表示当图 G 中的顶点 v 作为火源点时一个消防员所能保护的最多顶点数。图 G 的存活率 ρ(G) 定义为
，即当火随机地在图 G 的一个顶点燃起时，一个消防员最多能保护的顶点数的平均值。本文首先研究有限平面 4 · 8
2 格子图的存活率，分析格子图中点存活数的变化出有限 4 · 8
2 格子图的存活率的确切值；从而证明了对于无限平面 4 · 8
2 格子图， 每个回合使用一个消防员经过有限次保护后可以控制火的蔓延。
Abstract:
Firefighter Problem can be viewed as a discrete dynamic propagation model, which is closely related to the propagation of viruses, rumours or epidemics. Firefighter Prob- lem was introduced by Hartnell at the 25th Manitoba Conference on Combinatorial Mathematics and Computing. Let G be a connected graph with n(n ≥ 2) vertices. As- sume that a fire breaks out at a vertex v of G, a firefighter (or defender) chooses a set of vertices not yet on fire to protect; once a vertex has been chosen by the firefighter, it is considered protected or safe from any further moves of the fire. The process ends when the fire can no longer spread. Let sn(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v, which can be referred to as the surviving number for v. The surviving rate ρ(G) of graph G is de- fined to be the average percentage of vertices that can be saved when a fire randomly breaks out at one vertex of graph, i.e.,
. In this paper, we firstly study the surviving rate of finite 4 · 8
2 grids, and present the exact value of the surviving rate of finite 4 · 8
2 grids. Moreover, we prove that when fire breaks out at any vertex in infinite 4 · 8
2 grids, using one firefighter in each turn can control the spread of a fire after a limited amount of protection.