一类稀疏图的边存活率

郭文婷,孔将旭

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

1995年,Hartnell[1]在第25届曼尼托巴会议上提出了消防员问题。设G是一个有n个点的连通图,假设火源在G的某个顶点v处燃起,k个消防员任意选择k个没有着火的点进行保护,然后火蔓延到v的没有被保护且没着火的邻点,接着消防员又任意选择k个没有着火的顶点进行保护,火继续蔓延,火和消防员依次这样交替地在图G上移动。当火源无法再传播时,整个过程结束。

2002年,为了研究图的鲁棒性,Cai和Wang[2]提出了图的存活率的概念。当火在v处燃起时,用snk(v)表示k个消防员最多能保护的顶点数。当火随机地在图G的一个顶点燃起时,k个消防员最多能保护的顶点数的平均值称为图G的k-存活率,记为ρk(G),即

当k=1时,sn(v)=sn1(v),ρ(G)=ρ1(G)。

一般的,当火源点多个时,有对应的存活率的概念[3,4]。设F⊆V(G),|F|=f≥2为固定的正整数。snk(G,F)表示当火源在集合F中的点燃起时,k个消防员能保护的最大顶点数。当火随机地在图G的f个顶点燃起时,k个消防员最多能保护的顶点数的平均值称为图G的多火源存活率,记为ρk(G,f),即

1 主要结果

本文运用图染色理论中的经典方法“权转移”[7]证明以下结果:

推论4设G是一个n≥3且δ(G)=2的连通图。

推论5设G是一个至少有3个点的连通平面图且δ(G)=2。

2 定理3的证明

(1)

表达式(1)可以写成如下形式:

其中,

我们先通过权转移的方法证明如下断言。

根据上面的规则将初始权重新分配,得到新的权函数记为w′(uv)。由于权转移只是将权重新分配,不改变权的总和,因此,可得下面的等式

根据不等式(1)和断言1,有

引理2设G是一个至少有3个顶点的连通图,那么对任意的uv∈E(G),有

根据引理1和引理2,我们可以得到如下不等式:

因此,

定理3得证。

3 结 语

本文研究了最小度为2且平均度小于2.4的连通图的边存活率,用“权转移”的方法证明了这类稀疏图有正的边存活率,从火源的角度推广了定理1的结果。定理3中边存活率的下界不是最优的,可以通过设计更精细的权转移规则得到更好的下界,但寻找最好的下界并不是本文的主要目的。此外,定理3中最小度为2的条件是必须的,因为δ(K1,n-1)=1且ρ′(K1,n-1)→0(n→∞)。最后,定理3条件中的上界也不是最优的,因此可以提出下面两个问题:

问题1设k*,ε为正实数,G是一个有n个点m条边的连通图,满足mε。

问题2设ε为正实数,g*为正整数,G是一个g(G)≥g*且δ(G)=2的连通平面图,确定g*的阈值使得ρ′(G)>ε。