王维凡, 裘霞霜, 黄丹君
(浙江师范大学 数理与信息工程学院,浙江 金华 321004)
一类定向平面图的存活率
王维凡,裘霞霜,黄丹君
(浙江师范大学 数理与信息工程学院,浙江 金华321004)

防火问题;存活率;有向图;平面图
1995年,Hartnell[1]在第25届曼尼托巴组合数学与计算会议上提出了有限图G上的防火问题.假设火在图G的某个顶点v处开始燃烧,消防员选择某个未燃烧的顶点进行防护,消防员和火在图G上依次交替移动.一旦某个顶点被消防员防护下来,就称这个顶点在接下来的防火过程中一直都是受防护的.在消防员移动后,火继续向已燃烧顶点的其他邻点(未被防护的)蔓延.当火无法再继续蔓延时,就称整个防火过程结束了.2009年,文献[2]提出了图的存活率的概念.设G是含有n个顶点的连通图,并假设v是着火点.在整个防火过程中,称消防员最多能防护下来的顶点数为v的存活数,记为sn(v).当火随机地在G的某个顶点处燃起时,称消防员最多能防护下来的顶点数的平均比例为图G的存活率,记为ρ(G),公式表示为
类似地,给定一个正整数k≥1,若在防火的过程中,消防员每一步选择k个未燃烧的顶点进行防护,称其为k-防火问题.用snk(v)表示当点v为火源时,消防员最多能防护下来的顶点数.ρk(G)表示图G的k-存活率,公式表示为

文献[4-5]分别证明了:平面图是4-好的.这个结果最近被改进为:平面图是3-好的[6-7];文献[8]证明了围长至少为7的平面图是1-好的;使得平面图是2-好的一些充分条件则在文献[4,9-10]中被……