郭文婷,孔将旭

(中国计量大学 理学院,浙江 杭州 310018)

1995年,Hartnell[1]首次提出了消防员问题(Firefighter Problem)。设G是一个连通图,k是正整数。假设火在图G的一个顶点或多个点燃起,消防员每步选择k个没有着火的顶点加以防护,然后火蔓延到其未被保护且没有着火的邻点,火和消防员在图G上交替移动。当火没法再传播时,整个过程结束。

为了研究一个图的整体防火能力,蔡雷震和王维凡[2]首先提出了图的存活率的概念。设G是n阶连通图,snk(v)表示当v为火源点时,k个消防员最多能防护的顶点个数。当火等概率的在图G的一个顶点燃起时,k个消防员最多能保护的顶点数的期望称为图G的k-存活率,记为ρk(G),即

显然,0<ρk(G)<1,且对任意i>j,有ρi(G)≥ρj(G)成立。关于存活率和消防员问题的最新研究进展,请参阅王维凡和孔将旭的综述文献[3]。

1 几个预备引理设

G是简单平面图,我们用V(G),E(G),F(G),Δ(G)和δ(G)分别表示图G的顶点集、边集、面集,最大度和最小度。对v∈V(G),N(v)={u|uv∈E(G)},点v的度数d(v)=|N(v)|。对f∈F(G),用b(f)表示围成面f的周界,d(f)表示围成面f的周界的边数,称为f的度。一个度为k,至少为k或至多为k的点(面)分别称为k-点,k+-点或k--点(k-面,k+-面或k--面)。对于一条边uv,如果u是i-点,v是j-点,那么uv边称为(i,j)-边,并且用f1和f2表示与uv相关联的两个面,当uv是割边时,f1=f2。对于一个3-面[uvw],如果u是i-点,v是j-点,w是k-点,那么[uvw]面称为(i,j,k)-面。

引理1[8](平面图分离定理)设G是一个极大平面图,|V(G)|=n,T是G的任意一棵支撑树,则存在一条边e∈E(G)E(T)使得T+e中的唯一一个圈C满足圈内和圈外的点数都小于(2n)/3。

引理2[6]设G是平面图,T是G的任意一棵以r为根点的支撑树,则T中存在一条以x,y为端点的路P(xy),使得圈C=P(xy)+{xy}(xy可以不是G中的边,x,y≠r)满足圈内和圈外的点数都小于(2n)/3。……