令 G 是 n 个顶点的连通图。假设火在图 G 的某一点 u 处燃起,消防员选择一个未着火的顶点进行保护(一旦某个顶点被保护,则在整个过程中都将处千被保护状态),然后火蔓延到 u 的未加保护且没着火的邻点。依次下去,火和消防员交替地在图 G...令 G 是 n 个顶点的连通图。假设火在图 G 的某一点 u 处燃起,消防员选择一个未着火的顶点进行保护(一旦某个顶点被保护,则在整个过程中都将处千被保护状态),然后火蔓延到 u 的未加保护且没着火的邻点。依次下去,火和消防员交替地在图 G 上移动,直到火不能继续蔓延,整个过程结束。本文主要讨论了模 n 剩余类加群 Zn 在 k(k ≥ 2) 元逆闭子集的凯莱图上的消防员问题。首先考虑了凯莱图在二元逆闭子集上的消防员问题,这部分确定了凯莱图的结构并且提出了结构算法和该算法的 matlab 语言;其次研究了凯莱图在三元逆闭子集上的消防员问题, 这部分也确定了凯莱图的结构,并且考虑了点存活率,边存活率以及 MV S 问题;最后研究了凯莱图在大千三元逆闭子集上的消防员问题,这部分以点的标号顺序画出了凯莱图,按逆闭子集的阶数把凯莱图并分为两类,并考虑了凯莱图的任意一个顶点着火时,一个消防员能控制火的充要条件。展开更多
文摘令 G 是 n 个顶点的连通图。假设火在图 G 的某一点 u 处燃起,消防员选择一个未着火的顶点进行保护(一旦某个顶点被保护,则在整个过程中都将处千被保护状态),然后火蔓延到 u 的未加保护且没着火的邻点。依次下去,火和消防员交替地在图 G 上移动,直到火不能继续蔓延,整个过程结束。本文主要讨论了模 n 剩余类加群 Zn 在 k(k ≥ 2) 元逆闭子集的凯莱图上的消防员问题。首先考虑了凯莱图在二元逆闭子集上的消防员问题,这部分确定了凯莱图的结构并且提出了结构算法和该算法的 matlab 语言;其次研究了凯莱图在三元逆闭子集上的消防员问题, 这部分也确定了凯莱图的结构,并且考虑了点存活率,边存活率以及 MV S 问题;最后研究了凯莱图在大千三元逆闭子集上的消防员问题,这部分以点的标号顺序画出了凯莱图,按逆闭子集的阶数把凯莱图并分为两类,并考虑了凯莱图的任意一个顶点着火时,一个消防员能控制火的充要条件。
文摘消防员问题 (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 ·82 格子图的存活率,分析格子图中点存活数的变化出有限 4 ·82 格子图的存活率的确切值;从而证明了对于无限平面 4 ·82 格子图, 每个回合使用一个消防员经过有限次保护后可以控制火的蔓延。
