凯莱图上的消防员问题

The Firefighter Problem on Cayley Graph

摘要: 令 G 是 n 个顶点的连通图。假设火在图 G 的某一点 u 处燃起，消防员选择一个未着火的顶点进行保护(一旦某个顶点被保护，则在整个过程中都将处千被保护状态)，然后火蔓延到 u 的未加保护且没着火的邻点。依次下去，火和消防员交替地在图 G 上移动，直到火不能继续蔓延，整个过程结束。本文主要讨论了模 n 剩余类加群 Z_n 在 k(k ≥ 2) 元逆闭子集的凯莱图上的消防员问题。首先考虑了凯莱图在二元逆闭子集上的消防员问题，这部分确定了凯莱图的结构并且提出了结构算法和该算法的 matlab 语言；其次研究了凯莱图在三元逆闭子集上的消防员问题, 这部分也确定了凯莱图的结构，并且考虑了点存活率，边存活率以及 MV S 问题；最后研究了凯莱图在大千三元逆闭子集上的消防员问题，这部分以点的标号顺序画出了凯莱图，按逆闭子集的阶数把凯莱图并分为两类，并考虑了凯莱图的任意一个顶点着火时，一个消防员能控制火的充要条件。

Abstract: Let G be a connected graph with n vertices. Assume that a fire breaks out at a vertex v of G. A firefighter chooses a set of k 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 firefighter and the fire alternately move on the graph. The process ends when the fire can no longer spread. After the firefighter’s move, the fire makes its move by spreading to all vertices which are adjacent to the vertices on fire, except for those that are protected. In this paper, we discuss the firefighter problems in the Cayley graphs of additive group of integers modulo n with the k- element(k ≥ 2) inverse closed subset. Firstly we consider the firefighter problems on the 2-element inverse closed subset of Cayley graph, which determines the structure of Cayley graph and puts forward the structure algorithm and the matlab language of the algorithm. Secondly, we study the firefighter problems on the 3-element inverse closed subset of Cayley graph, which also determines the structure of Cayley graph and considers surviving rate, edge surviving rate and MV S problem. Finally, we discuss the firefighter problems on the k-elements(k ≥ 4) inverse closed subset of Cayley graph, in which we draw the Cayley graph in order of points, and divide the Cayley graph into two categories according to the order of the inverse closed subset. Moreover, while any vertex of Cayley graph is on fire, we consider the sufficient and necessary conditions that a firefighter can control the fire.