不含短圈的平面图的存活率

作者：王维凡^*; 胡嘉程

来源：应用数学学报, 2023, 46(04): 493-506.

• 消防员问题
• 存活率
• 平面图
• 圈

设G是一个n-阶连通图(n≥2).假设火在G的某点v处燃起,消防员选择一个未着火的顶点进行保护,然后火蔓延到v的未被保护且没有着火的邻点.当火在点v处燃起时,消防员最多能保护到的顶点数记为sn(v).定义■为G的存活率.容易看到0 <ρ(G)<1.本文证明了:若平面图G不含长度从4到11的圈,则ρ(G)>1/481.

• 单位
  浙江师范大学